[JavaScript/section 9] 02 - 경로 탐색(인접 리스트)

📌 02 - 경로 탐색(인접 리스트)

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

 

이전 문제와 같은 문제이지만 인접 행렬이 아닌 인접 리스트를 이용해보려고 한다. 정점이 적다면 인접 행렬로 풀어도 되지만 무수히 많다면 메모리 낭비, 시간 복잡도 증가와 같은 문제점이 발생한다. 💩💩

이를 해결할 수 있는 방법으로 인접 리스트를 이용하는 방식이 존재한다.

v 정점(행)에서 이동 가능한 정점을 각각 배열에 추가한다.

 

📝 풀이 방법

v - 현재 정점, i - 배열의 인덱스, ch - 해당 정점을 지났는지 체크하는 배열

graph[v][i] - 현재 정점에서 이동할 수 있는 정점으로 node 변수에 저장

• 재귀를 돌면서 ch[node]가 0이라면 v 정점에서 node 정점으로 이동할 수 있다는 것이므로 해당 정점으로 이동했음을 나타내기 위해 ch[node]를 1로 재할당한다.
• DFS(node) 함수를 호출하고 종료가 되면 다음에 해당 정점으로 이동할 수 있도록 ch[node]를 0으로 다시 재할당한다. (백트래킹)
• v와 n이 같다면 하나의 경우가 만들어진 것이므로 answer에 1을 더해준다.

주의할 점❗ 1번 정점에서 시작하므로 ch 배열의 1번 인덱스를 1로 초기화한 다음 재귀를 시작해야 한다.

function solution(n, arr) {
  let answer = 0;
  const graph = Array.from(Array(n + 1), () => Array());
  const 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++) {
        const node = graph[v][i];

        if (ch[node] === 0) {
          ch[node] = 1;
          DFS(node);
          ch[node] = 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));