[ 자바스크립트(JavaScript) ] section09 - 2 - 경로 탐색(인접행렬)

📍 section09 - 2 - 경로 탐색(인접행렬)

방향 그래프가 주어지면 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

 

이 문제는 DFS를 이용해서 풀 수 있다. 경로의 가짓수만 출력하는 것이 아니라 올바르게 이동했는지 알기 위해 path 변수를 추가했다.

 

1. 2차원 배열의 graph를 선언하여 정점과 간선의 정보를 넣는다.
2. visited 배열을 선언하여 이미 지나온 곳은 건너뛰고 진행한다.
3. DFS의 종료 조건은 v가 n과 같을 때이다.
4. 인접 행렬이므로 반복문으로 모든 정점을 탐색해야 한다.
5. DFS 함수를 돌리기 전 1번 정점에서 시작하므로 visited[1]=1을 선언한다. 그렇지 않으면 1번 정점에 중복 방문한다.

 

 

728x90

 

let n = 5;
let m = 9;
let arr = [
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 1],
    [2, 3],
    [2, 5],
    [3, 4],
    [4, 2],
    [4, 5],
];
 
console.log(solution(n, m, arr));
 
function solution(n, m, arr){
  let visited = Array.from({length: n+1});
  let graph = Array.from(Array(n+1), () => Array(n+1).fill(0));
  let path = []
  let cnt=0;
 
  for (let [a, b] of arr) graph[a][b] = 1;  // graph에 값 넣기
 
  function DFS(v){
    if (v === n){
      console.log(path);  // 경로 출력
      cnt++;  // 경로의 가짓 수 출력
    }else{
      for (let i=1; i<=n; i++){
        if (!visited[i] && graph[v][i]){
          visited[i] = 1;
          path.push(i)
          DFS(i);
          visited[i] = 0;
          path.pop()
        }
      }
    }
  }
 
  path.push(1);
  visited[1]=1;
  DFS(1);
  return cnt;
}
 
👉🏽
[ 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