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

✏️ 입력설명

첫번째 줄에는 정점의수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.

✏️ 출력설명

총 가지수를 출력한다.

✏️ 입력예제 1

1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

✏️ 출력예제 1

6

const solution = (n ,arr) => {
  let answer = 0;
  let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); // 인접화를 위한 2차열 배열 생성 1번 index 번호 부터 사용하기 때문에 n + 1 개의 행, 열의 2차월 배열을 만듬
  let ch = Array.from({length: n+1}, () => 0); // 노드 방문 체크를 위한 배열
  for (let [a, b] of arr ) {
    graph[a][b] = 1;
  }
  
  const DFS = (v) => { // v = vertex
    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));