9-3. 경로 탐색(DFS-인접 리스트 : 노드 개수가 많을 때 적용)

문제

방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 총 6 가지입니다.

풀이

function solution(n, arr) {
  let answer = 0;
  let graph = Array.from(Array(n + 1), () => Array());
  let ch = Array.from({ length: n + 1 }, () => 0);
  let path = [];
  for (let [a, b] of arr) {
    graph[a].push(b);
  }

  function DFS(v) {
    if (v === n) {
      answer++;
      console.log(path);
    } else {
      for (let nv of graph[v]) {
        if (ch[nv] === 0) {
          ch[nv] = 1;
          path.push(nv);
          DFS(nv);
          ch[nv] = 0;
          path.pop();
        }
      }
    }
  }
  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));

풀이 방법

인접 행렬로 문제를 풀었을 때에는 행렬 배열을 생성할 때 모두 0으로 된 배열을 만들었었는데 이제 노드 개수가 만약 10000개~100000개 일 때에는 시간 복잡도가 크게 높아져서 노드가 많을 때에는 인접 리스트 방식으로 푸는 것이 좋습니다.

 

인접 리스트란 빈 배열을 전체 arr의 개수 +1 만큼 생성하여 빈 배열 안에 원소를 넣어 문제를 푸는 방식입니다. 노드 개수가 많아도 빠르게 풀 수 있는 더 효율적인 방법이라고 할 수 있습니다.