[인접 행렬]경로 탐색

[인접 행렬]경로 탐색

문제

문제풀이

인접행렬

인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식

arr[i][j]: 노드 i(행)에서 j(열)로 가는 간선이 있으면 1, 아니면 0_단방향그래프의 경우

인접 행렬의 특성을 고려하여 문제에서의 경로 경우수에 만족하는 인접 행렬을 생성할 경우 다음과 같이 표현할 수 있다.

인접 행렬

행을 기준으로 열로 이동했을 때 경로가 있다면 1을, 아니면 0을 배열 내에 할당한다.

각 행은 정점(현재 있는 위치), 각 열은 다음 행선지 후보군 이라고 정리할 수 있다.

이를 노드를 통해 깊이 탐색 과정으로 바꿔 그려 본다면 다음과 같이 나온다.

간선 이동에 대한 DFS 탐색

코드

function solution(n, arr) { let answer = 0; let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); let ch = Array.from({length: n + 1}, () => 0); for(let [a, b] of arr) { graph[a][b] = 1; } function DFS(v) { if(v === n) answer++; else { for(let i = 1; i <= n; i++) { if(graph[v][i] === 1 && ch[i] === 0) { ch[i] = 1; DFS(i); ch[i] = 0; } } } } ch[1] = 1; //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));

from http://choi95.tistory.com/124 by ccl(A) rewrite - 2021-08-09 21:26:22