[ 자바스크립트(JavaScript) ] section09 - 3 - 경로 탐색(인접리스트)

📍 section09 - 3 - 경로 탐색(인접리스트)

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

 

이전과 동일한 문제지만 이번에는 인접 리스트를 활용해서 푸는 문제다. 만약에 그래프를 이용한 문제에서 정점의 개수가 10,000개 이상이라면 인접리스트를 사용하자.(인접 행렬은 정점의 개수만큼 반복문을 돌아야 하기 때문에 비효율적이다.) 이 문제도 마찬가지로 DFS를 이용해서 풀 수 있다. 경로의 가짓수만 출력하는 것이 아니라 올바르게 이동했는지 알기 위해 path 변수를 추가했다.

 

1. 인접 리스트의 반복문의 범위는 graph[v].length까지
2. 인접 행렬처럼 정점끼리 연결되어 있는지 확인하는 작업(graph[v][i]===1)이 필요 없다. 왜냐하면 인접 리스트는 정점끼리 이미 연결된 값만 넣기 때문이다. 대신 visited 배열로 방문했는지 여부만 조건에 걸어주면 된다.
3. 다음 DFS함수를 실행할 때는 DFS(graph[v][i])를 넣어줘야 한다.

 

 

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 graph = Array.from(Array(n+1), () => Array());
  let visited = Array.from({length: n+1}, () => 0);
  let cnt=0;
  let path=[];

  for (let [a, b] of arr) graph[a].push(b);  // 인접 리스트 만들기

  function dfs(v){
    if (v === n){
      console.log(path);
      cnt++;
    }else{
      for (let i=0; i<graph[v].length; i++){
        if (!visited[graph[v][i]]){
          visited[graph[v][i]]=1;
          path.push(graph[v][i])
          dfs(graph[v][i]);
          visited[graph[v][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