2022/05/01) 3. 경로탐색(인접리스트) [그래프와 탐색(DFS, BFS(넓이우선))]

1. 문제

<경로 탐색>
: 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성한다. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지수는 총 6가지다.
(첫째 줄에는 정점의 수 N와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.)
총 가지수를 출력한다.

2. 해결 방법

1. 정점 개수가 많을 때 인접 행렬을 이용해서 풀면 정점 개수만큼 for문을 돌려서 조건을 확인해야 한다. 만약 정점 개수가 만 개라면 for문을 만 번 돌려야 하는 것이다.
   그리하여 이럴 경우엔 인접 리스트를 이용해서 푼다.
2. 인접 리스트의 경우엔 행은 그대로 정점 번호가 될 것이므로 1부터 시작해야 한다. 열은 만약 해당 정점이 2라는 정점을 갈 수 있다고 하면, 해당 정점행에 2값을 push해서 넣을 것이므로 굳이 정점수대로 열을 만들지 않아도 된다.
   => let graph = Array.from(Array(n+1), ()=>Array()); //인접리스트배열 생성
   => graph[a].push(b); //인접리스트 생성
3. 그렇다면 for문에서 변수i는 0부터 g[v].length까지 돌아야 한다. 그렇게 되면 v정점에서 갈 수 있는 정점은 graph[v][i]가 된다.
4. 인접행렬에서는 모든 정점개수만큼 열을 생성해서 해당 정점이 그 정점을 지나가면 1, 지나가지 않으면 0으로 표현했지만, 인접 리스트에서는 해당 정점이 그 정점을 지나가면 그 정점값을 push해서 넣어줬다. 그러므로 for문의 if조건문에서 0인지 1인지 확인할 필요가 없다. 그저 이전에 지나간 정점인지 아닌지만 확인해주면 된다.
   => if(ch[graph[v][i]] === 0) //지나가는 정점값을 push해줬으므로, 결국 graph[v][i]엔 정점값이 들어있음.
5. check설정해주는 거 잊지 말자. 그리고 DFS호출해서 값을 넘겨줄 땐 꼭 정점값을 넘겨줘야 하므로 graph[v][i]를 넣어주는 걸 잊지 말자!!!

3. 정답

        <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=[];
                for(let [a,b] of arr){
                    graph[a].push(b); //push
                }
                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]); //정점을 넘겨야 한다.
                                ch[graph[v][i]] = 0;
                                path.pop();
                            }
                        }
                    }
                }
                ch[1]=1;
                path.push(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>

        <script> //for..of문으로 이렇게도 가능
            function solution(n, arr){  
                let answer=0;
                let graph=Array.from(Array(n+1), ()=>Array());
                let ch=Array.from({length:n+1}, ()=>0);
                for(let [a, b] of arr){
                    graph[a].push(b);
                }
                function DFS(v){
                    if(v===n){
                        answer++;
                    }
                    else{
                        for(let nv of graph[v]){
                            console.log(nv)
                            if(ch[nv]===0){
                                ch[nv]=1;
                                DFS(nv);
                                ch[nv]=0;
                            }
                        }
                    }
                }
                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>

4. 소감

야호 야호 미루지 않고 하니까 까먹은게 없어서 재밌땅