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

문제

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

풀이

function solution(n, arr) {
  let answer = 0;
  let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
  //   console.log(graph);
  let ch = Array.from({ length: n + 1 }, () => 0);
  let path = [];
  for (let [a, b] of arr) {
    graph[a][b] = 1;
  }
  function DFS(v) {
    if (v === n) {
      answer++;
      console.log(path);
    } else {
      for (let i = 1; i <= n; i++) {
        if (graph[v][i] === 1 && ch[i] === 0) {
          ch[i] = 1;
          path.push(i);
          DFS(i);
          ch[i] = 0;
          path.pop();
        }
      }
    }
  }
  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));

 

풀이 방법

먼저 연결된 그래프의 모양을 행렬 데이터 배열로 만들어서 연결되어 있으면 1로 표시합니다.

 

그리고 DFS함수에서 for문을 1부터 n까지 하되 graph [자신][연결대상] 이 1로 연결되어 있고 ch 배열에서 0일 때 ( 아직 사용하지 않은 원소라는 뜻) DFS를 재귀로 진행하여 풀이했습니다.