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