61.경로 탐색 - 인접행렬(노드개수가 적을 때) - 그래프, 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(n + 1).fill(0)); // 인접화를 위한 2차열 배열 생성 1번 index 번호 부터 사용하기 때문에 n + 1 개의 행, 열의 2차월 배열을 만듬
let ch = Array.from({length: n + 1}, () => 0); // 노드를 방문 했냐 안햇냐를 check 하기 위한 배열 생성
let path = [];
for (let [a, b] of arr) { // arr 탐색를 값 1개 씩 탐색하는것
console.log(a, b)
graph[a][b] = 1 // 방향 그래프에서 graph arr 에 1로 체크 거는것 : 입력 받은 가지의 수를
}
function DFS(v) {
if(v === n ) {
answer++;
console.log(path);
}
else {
for(let i = 1; i <= n; i++) {
if(graph[v][i] === 1 && ch[i] === 0) { // graph 배열에 1로 체크 되어 있고, check arr 에 0으로 체크 되어 있을경우(이거는 한번도 안간경우)
ch[i] = 1; // 한번 왔다고 ch 걸어 줘야 되고
path.push(i) // path 출력을 위해서 path arr 이 push 해줌
DFS(i); // 다시 재귀로 다음 번호로 for loop 돌어서 v === n 까지의 경로를 탐색
ch[i] = 0; // 탐색 종료 후, back 을 하기 전에 check 된것을 다시 0 으로 초기화 하고 back 해줘야 함
path.pop() // check 를 풀었으니까 path 에서도 저장된 값 pop 해서 빼내야 됨
}
}
}
}
path.push(1)
ch[1] = 1; // DFS 돌기 전에 check arr 에 1은 방문했다고 check 를 걸어 줘야 재귀 돌때 다시 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>
</body>
Leave a comment