62.경로 탐색 - 인접리스트(노드개수가 많을 때) - 그래프, DFS
Updated:
🔍 문제
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요.
아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는
🔹 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다.
그 다음부터 M줄에 걸쳐 연결정보가 주어진다.
🔹 출력 설명
총 가지수를 출력한다.
🔹 입력예제 1
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
🔹 출력 예제 1
6
📌 풀이
<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()); // 행은 node 의 개수 + 1 개 만큼 하고 열은 그냥 빈 자리로 남겨둠
let ch = Array.from({length : n + 1}, () => 0);
let path = [];
for(let [a, b] of arr) {
graph[a].push(b) // 인접 리스트가 됨
}
function DFS(v) {
if (v === n) {
answer ++;
console.log(path)
}
else {
for(let i = 0; i <= graph[v].length; i++) { // 그래프 행의 길이만큼 for loop 돌면 됨
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();
}
}
}
}
path[0] = 1;
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>
Leave a comment