[JavaScript/section 9] 01 - 경로 탐색(인접 행렬)

📌 01 - 경로 탐색(DFS-인접 행렬: 노드 개수가 적을 때)

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

 

다음과 같이 방향 그래프가 주어지면 인접 행렬로 표현할 수 있어야 한다.

인접 행렬

v 정점(행)에서 i 정점(열)으로 가는 경로가 존재한다면 1, 존재하지 않으면 0으로 표시한다.

 

📝 풀이 방법

v - 현재 정점, i - 마지막으로 도달해야하는 정점

ch - 해당 정점을 지났는지 체크하는 배열

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

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

1번 정점에서 5번 정점으로 가는 경로중 1 2 3 4 5를 지나는 경로

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

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

  function DFS(v) {
    if (v === n) {
      answer++;
    } 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;
}

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));