<경로 탐색>
: 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성한다. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지수는 총 6가지다.
(첫째 줄에는 정점의 수 N와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.)
총 가지수를 출력한다.
인접행렬을 만든다.
(graph배열을 만들고, arr를 for...of문으로 돌려서 graph[a][b]=1; 해주기)- for문을 돌려서 각 노드에 접근하는데, 모든 노드에 접근하면 안되므로 조건을 넣는다.
첫 번째 조건
으로는, D(1)부터 시작하므로 노드 1에서 가는 노든지 안가는 노든지 확인하기 위해서 graph[1][i]===1 해준다. (이건 예시고 실제로는 graph[v][i]===1 해줘야 함)
두 번째 조건
으로는, 이미 거쳤던 정점을 다시 돌아가서 거치지 않도록 하기 위해 ch배열을 통해 거쳤던 정점인지 아닌지 판단한다. ch[i]===0;
=> if(graph[v][i]===1 && ch[i]===0){}- 위의 조건에 통과할 경우,
지나갈 수 있는 정점
이다. 그러면 이 정점은 거친 정점이 되므로, ch[i]=1;을 해주고 DFS(i);를 호출해서, 다음으로 거칠 정점을 찾는다. 그리고 해당 정점이 back해서 돌아올 때 거쳤던 노드들은 다시 거치지 않은 노드상태로 해주어야 하므로, ch[i]=0;을 해준다.- 마지막으로 N정점으로 가는
모든 경로의 가지수를 출력
해야 하므로, v===n(정점이 5)일 때 answer++; 해준다.- 위처럼 하면
틀린 답
이 나온다. 그 이유는 DFS(1)을 호출할 때,ch[1]=1;을 해주지 않았기 때문이다. 그리하여 1은 거치지 않은 노드로 판정이 되어 다른 노드에 갔다가 다시 노드1로 돌아 와서 저런 답이 나온거다. 그러므로 ch[1]=1; 을 해주고 DFS(1);을 호출하여 준다.
- 정리하면 for문을 1부터 N까지 다 돌려서, 갈 수 있는지 없는지 확인하는거다!!! 그리고 체크 중요!
<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>
나는 ch배열을 생각해내지 못했다. 이전에 조합에서 했던 for문으로 구현할 생각을 했다. 그런데 직접 그림을 그려서 생각해보니, 노드가 오름차순 혹은 내림차순으로 일정하게 가는 게 아니므로 이건 엉터리라는 걸 알았다. 그래서 그냥 바로 강의봤다. 그리고 이전에 거쳤던 경로는 거치면 안된다라는 생각을 하지 못해서, 뭐 이런 이상한 답이 다있지라고 생각했다. 흠...