[알고리즘/인프런] 경로탐색(인접 리스트)

문제

---

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

 

 

풀이

---

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

  for (let [a, b] of arr) {
    graph[a] = [...graph[a], b];
  }

  console.log(graph);

  function DFS(v) {
    if (v === n) answer += 1;
    else {
      for (let i = 0; i < graph[v].length; i++) {
        const next = graph[v][i]; // 정점 번호
        if (ch[next] === 0) {
          ch[next] = 1;
          DFS(next);
          ch[next] = 0;
        }
      }
    }
  }
  ch[1] = 1;
  DFS(1);
  return answer;
}

효율성을 위해 각 정점에서 갈 수 있는 정점 번호를 리스트로 저장한다.
그러면 각 정점에서 graph[v].length만큼만 돌면 된다.

 

<인접 리스트 vs. 인접 행렬>

그래프의 노드 개수가 많을 때는 인접 리스트를 쓰고, 노드 개수가 100개 이하면 인접 행렬을 써도 무방하다고 한다.