2022/04/29) 2. 경로탐색(인접행렬) [그래프와 탐색(DFS, BFS(넓이우선))]

1. 문제

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

2. 해결 방법

1. 인접행렬을 만든다. (graph배열을 만들고, arr를 for...of문으로 돌려서 graph[a][b]=1; 해주기)
2. for문을 돌려서 각 노드에 접근하는데, 모든 노드에 접근하면 안되므로 조건을 넣는다.
   첫 번째 조건으로는, D(1)부터 시작하므로 노드 1에서 가는 노든지 안가는 노든지 확인하기 위해서 graph[1][i]===1 해준다. (이건 예시고 실제로는 graph[v][i]===1 해줘야 함)
   두 번째 조건으로는, 이미 거쳤던 정점을 다시 돌아가서 거치지 않도록 하기 위해 ch배열을 통해 거쳤던 정점인지 아닌지 판단한다. ch[i]===0;
   => if(graph[v][i]===1 && ch[i]===0){}
3. 위의 조건에 통과할 경우, 지나갈 수 있는 정점이다. 그러면 이 정점은 거친 정점이 되므로, ch[i]=1;을 해주고 DFS(i);를 호출해서, 다음으로 거칠 정점을 찾는다. 그리고 해당 정점이 back해서 돌아올 때 거쳤던 노드들은 다시 거치지 않은 노드상태로 해주어야 하므로, ch[i]=0;을 해준다.
4. 마지막으로 N정점으로 가는 모든 경로의 가지수를 출력해야 하므로, v===n(정점이 5)일 때 answer++; 해준다.
5. 위처럼 하면 틀린 답이 나온다. 그 이유는 DFS(1)을 호출할 때,ch[1]=1;을 해주지 않았기 때문이다. 그리하여 1은 거치지 않은 노드로 판정이 되어 다른 노드에 갔다가 다시 노드1로 돌아 와서 저런 답이 나온거다. 그러므로 ch[1]=1; 을 해주고 DFS(1);을 호출하여 준다.

• 정리하면 for문을 1부터 N까지 다 돌려서, 갈 수 있는지 없는지 확인하는거다!!! 그리고 체크 중요!
  

3. 정답

        <script> //path배열을 생성하여 어떤 경로로 가는지도 출력해보자.
            function solution(n, arr){  
                let answer=0;
                let graph = Array.from(Array(n+1), ()=>Array(n+1).fill(0)); //이차원배열(인접행렬) 1번인덱스부터 사용할 것이므로 +1해줌
                let ch=Array.from({length:n+1}, ()=>0);
                path=[]; 
                for(let [a,b] of arr){
                    graph[a][b]=1;
                }
                function DFS(v){
                    if(v===n){//정점이 5일때
                        answer++; 
                        console.log(path);
                    } 
                    else{
                        for(let i = 1; i <= n; i ++){
                            if(graph[v][i]===1 && ch[i]===0){
                                    ch[i]=1;
                                    path.push(i);
                                    DFS(i);
                                    ch[i]=0;
                                    path.pop();
                            }
                        }
                    }
                }
                path.push(1);
                ch[1]=1; //이거 해주고 DFS(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. 내 코드와 비교

나는 ch배열을 생각해내지 못했다. 이전에 조합에서 했던 for문으로 구현할 생각을 했다. 그런데 직접 그림을 그려서 생각해보니, 노드가 오름차순 혹은 내림차순으로 일정하게 가는 게 아니므로 이건 엉터리라는 걸 알았다. 그래서 그냥 바로 강의봤다. 그리고 이전에 거쳤던 경로는 거치면 안된다라는 생각을 하지 못해서, 뭐 이런 이상한 답이 다있지라고 생각했다. 흠...