경로 탐색(인접행 및 인접리스트)

인접행렬(비효율)

코드

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

    function DFS(v) {
      if (v === n) {
        answer++;
      } else {
        for (let i = 1; i <= n; i++) {
          if (ch[i] === 0 && dy[v][i] === 1) {
            ch[i] = 1;
            DFS(i);
            ch[i] = 0;
          }
        }
      }
    }

    ch[1] = 1
    DFS(1);

    return answer;
  }

우선 이 방법은 숫자가 커지면 효율적이지 못한 코드이다.

문제점

dy에 모든 간선 정보를 입력해준다. 이를 기반으로 처음부터 끝까지 모두 탐색하여 정답을 구하는 것이지만 숫자가 커지면 비효율적이다.

따라서 이렇게 푸는 방법은 지양해야한다.

---

인접리스트

코드

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

    function DFS(v) {
      if (v === n) answer++;
      else {
        for (let nv of graph[v]) {
          if (ch[nv] === 0) {
            ch[nv] = 1;
            DFS(nv);
            ch[nv] = 0;
          }
        }
      }
    }

    ch[1] = 1;
    DFS(1);

    return answer;
  }

이 코드는 효율적인 풀이이다.

해결 방법

위 사진처럼 1번 노드에 연결된 노드를 다 리스트에 넣는 인접 리스트 방법을 사용했다.

1번 노드에서 연결된 노드에 가서 쭉 연결된 노드를 탐색하고 5번 노드에 도착하면 answer의 값을 1 올리도록 했다.

주의할 점은 DFS(1)을 하기 전, ch[1] = 1를 해줘야 1번 노드를 더 이상 가지 않는다.(ch는 방문한 노드를 1로 저장한다.)

이 방법을 사용하면 모든 노드를 탐색하지 않아도 된다.