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

문제 

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

 

풀이

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

  // 인접행렬
  for (let [a, b] of arr) {
    graph[a][b] = 1;
  }

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

  // 시작점 방문 표시
  ch[1] = 1;
  DFS(1);
  return answer;
}

그래프 탐색 시 다음 재귀 함수를 호출할 때 DFS(i) 로 호출한다. 각 for문을 돌면서 가능한 다음 정점이 i 가 되고, 이것을 다음 시작점으로 넘겨주기 위해서이다.

또 DFS(1)로 시작점을 넘겨주면서 ch[1]=1로 체크 표시를 하지 않아 다시 시작점으로 되돌아가는 문제가 있었는데 이 부분에 유의해야겠다.