[JS] 코딩 테스트 문제 : 경로 탐색 [인접행렬]

문제 : 경로 탐색(인접행렬)

문제 설명

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

▣ 입력설명

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

▣ 출력설명

총 가지수를 출력한다.

▣ 입력예제 1

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

▣ 출력예제 1

6
1 2 5
3 4

내코드

function solution(n, arr) {
  let answer = 0;

  // 인접행렬을 구현한 2 차원 배열
  let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));

  // 주어진 방향그래프 arr 를 활용해 인접행렬 구현
  arr.forEach(([s, e]) => (graph[s][e] = 1));
  console.log(graph);

  // 재귀함수 DFS
  //  current : 현재 노드 번호 1부터 시작하므로 1이 기본값
  //  chkArr : 현재까지 방문한 노드 순서대로 저장한 배열 시작값은 1 이므로 [1] 이 기본값
  function DFS(current = 1, chkArr = [1]) {
    // n 번까지 도착했다면 정답 1 증가
    if (current === n) {
      console.log("완성된 경로:", ...chkArr);
      return ++answer;
    }

    // 현재 번호를 배열을 순회
    for (let i = 1; i <= n; i++) {
      // 이동 가능한 노드 중 지금까지 방문안한 노드의 경우 (chkArr 들어있지 않다면 아직 방문하지 않은 노드를 의미)
      // 그 노드의 번호를 current,chkArr 에 번호를 추가한 배열을 매개변수로 재귀함수 DFS 다시 호출
      if (graph[current][i] > 0 && !chkArr.includes(i))
        DFS(i, [...chkArr, i]);
    }
  }

  DFS();
  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. 2 차원 배열 graph 을 생성 후 주어진 방향그래프 arr 를 활용해 인접행렬 구현
2. 노드들을 순회하며 경로를 점검하기 위해 방문할 노드번호를 의미하는 인자 current, 현재까지 방문한 노드 순서대로 저장한 배열 인자 chkArr 를 가지는 재귀함수 DFS 선언
3. 함수 안에서 현재 번호 current 를 토대로 인접행렬 배열 graph 를 순회하면서 방문할 수 있는 노드를 확인 후 방문안한 노드의 경우 그 노드의 번호와 chkArr 에 번호를 추가한 배열을 각각 매개변수로 재귀함수 DFS 다시 호출
4. 위 과정을 반복하면서 만약 n 번 노드까지 도착한 경우 함수를 종료하고 정답 1 증가

보완할 수 있는 부분

현재까지 방문한 노드들을 확인하기 위해 Array.includes 메서드를 사용하여 현재까지 저장된 노드 배열을 탐색하므로 시간 복잡도가 증가한다.

위 방식을 보완하기 위해 노드들의 개수만큼 확인용 배열을 생성해 재귀함수에서 노드들의 경로를 저장하는 과정에 같이확인용 배열에 현재 노드들의 방문 여부를 0,1 구분해 저장하고 초기화 하여 확인에 사용

// 기존코드
for (let i = 1; i <= n; i++) {
  if (graph[current][i] > 0 && !chkArr.includes(i))
    DFS(i, [...chkArr, i]);
}

// 보완코드
// 체크용 배열 ch 생성부분 : let ch = Array.from({ length: n  + 1}, () =>  0);  
for (let i = 1; i <= n; i++) {
  if (graph[v][i] === 1 && ch[i] === 0) {
    ch[i] = 1; // 체크용 배열에 현재 노드방문 여부를 체크용도로 1을 저장
    path.push(i); // 노드의 경로를 저장할 임시 배열에 값 추가
    DFS(i);

    ch[i] = 0; // 재활용을 위한 초기화
    path.pop(); // 재활용을 위해 마지막 값 제외
  }
}

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/unit/64152