방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6 가지입니다.
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.
총 가지수를 출력한다.
9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
6
function solution(n, array) {
let answer = 0;
let graph = Array.from(Array(n + 1), () => Array());
let check = Array.from({ length: n + 1 }, () => 0);
let path = [];
for (let [a, b] of array) {
graph[a].push(b);
}
function DFS(v) {
if (v === n) {
console.log(path);
answer++;
} else {
for (let i = 0; i < graph[v].length; i++) {
if (check[graph[v][i]] === 0) {
check[graph[v][i]] = 1;
path.push(i);
DFS(graph[v][i]);
check[graph[v][i]] = 0;
path.pop();
}
}
}
}
path.push(1);
check[1] = 1;
DFS(1);
return answer;
}
let array = [
[1, 2],
[1, 3],
[1, 4],
[2, 1],
[2, 3],
[2, 5],
[3, 4],
[4, 2],
[4, 5],
];
console.log(solution(5, array));