[인접 리스트]경로 탐색

문제

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));