[인접 행렬]경로 탐색

문제

 

문제풀이

인접행렬

• 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식
• arr[i][j]: 노드 i(행)에서 j(열)로 가는 간선이 있으면 1, 아니면 0_단방향그래프의 경우

인접 행렬의 특성을 고려하여 문제에서의 경로 경우수에 만족하는 인접 행렬을 생성할 경우 다음과 같이 표현할 수 있다.

인접 행렬

행을 기준으로 열로 이동했을 때 경로가 있다면 1을, 아니면 0을 배열 내에 할당한다.

각 행은 정점(현재 있는 위치), 각 열은 다음 행선지 후보군 이라고 정리할 수 있다.

 

이를 노드를 통해 깊이 탐색 과정으로 바꿔 그려 본다면 다음과 같이 나온다.

간선 이동에 대한 DFS 탐색

 

코드

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