9-3) 경로 탐색(인접리스트)

김예지·2021년 9월 8일
0

문제

앞의 문제(9-2)와 동일


문제 풀이

예습 이론

  • 앞 문제에서 사용했던 인접행렬은, 시간복잡도가 높고 메모리도 많이 차지한다. 그러나 인접리스트는 시간복잡도가 낮으며 메모리도 많이 차지하지 않는다. 따라서 노드의 개수가 많아지면 인접리스트를 사용하는것이 좋다.
  • 인접리스트의 원리는 다음과 같다. 앞에서 봤던 인접행렬과 비교해보자!

코드

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(n, arr){  
                let answer=0;
                let graph=Array.from(Array(n+1), ()=>Array()); //인접리스트 만듦
                let ch=Array.from({length:n+1}, ()=>0);
                let path=[]; //테스트 코드 path(경로)
                //인접리스트
                for(let [a, b] of arr){
                    graph[a].push(b); 
                }
                console.log(graph);

                function DFS(v){
                    if(v===n){
                        answer++;
                        console.log(path);
                    }
                    else{
                        for(let i=0; i<graph[v].length; i++){
                            if(ch[graph[v][i]]===0){
                                ch[graph[v][i]]=1;
                                path.push(graph[v][i]);
                                DFS(graph[v][i]); //push한것에서부터 출발 
                                ch[graph[v][i]]=0;
                                path.pop();
                            }
                        }
                    }
                }
                path.push(1); //출발점 1은 무조건 처음에 push
                ch[1]=1;
                DFS(1);
                return answer;
            }

            let arr=[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]];
            console.log(solution(5, arr));
        </script>
    </body>
</html>
profile
내가 짱이다 😎 매일 조금씩 성장하기🌱

2개의 댓글

comment-user-thumbnail
2021년 9월 18일

9/18
그림 그려보면서 차근차근 풀어보기

답글 달기
comment-user-thumbnail
2021년 9월 23일

9/23

답글 달기