[인접 리스트]경로 탐색

[인접 리스트]경로 탐색

문제

https://choi95.tistory.com/124

문제풀이

이전 경로 탐색을 구하는 과정에서 인접 행렬을 사용하여 정점으로 가는 가지 수를 구하였다.

하지만 각 정점에 대해서 다음 정점으로 갈 수 있는 후보군을 행(현재 정점)과 열(다음 정점)에 저장한다면 탐색 과정에서불필요한 인덱스 요소까지 일일히 확인하면서 순회해야 되는 문제가 발생한다.

현재는 열(다음 정점)의 수가 적어 크게 상관은 없으나 후보군이 무수히 많지만 그 중 실제 갈 수 있는 경로의 수가 극소수이다면모든 경로를 갈 수 있는지 순회하는 것은 시간복잡도 상 매우 비효율적이다.

인접 리스트

n개의 정점을 각각에 대해 인접한 정점들의 리스트로 만드는 것

연결 가능한 모든 경우의 수를 저장해서 보여주는 인접행렬과는 다르게 연결되어 있는 경우에만 저장_메모리를 덜 사용

인접 리스트

코드

function solution(n, arr) { let answer = 0; let graph = Array.from(Array(n + 1), () => Array()); //각 정점이 연결되어 있는 정점은 상이하기 때문에 2차원 배열을 빈 공백으로 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 i = 0; i < graph[v].length; i++) { //연결되어 있는 정점의 갯수만큼만 순회 if(ch[graph[v][i]] === 0) { ch[graph[v][i]] = 1; DFS(graph[v][i]); ch[graph[v][i]] = 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));

from http://choi95.tistory.com/125 by ccl(A) rewrite - 2021-08-11 20:26:34