[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 listArr = Array.from(Array(n + 1), () => new Array());

  // 재귀함수 과정에서 방문한 노드들을 확인 하기 위한 체크용 배열
  // (배열에 l 번째 위치에 1 이 위치한 경우 숫자 l 노드에 방문한 것을 의미)
  let ch = new Array(n + 1).fill(0);
  ch[1] = 1; // 기본적으로 1번 노드 추가

  // 주어진 연결정보를 listArr에 인접리스트로 구현
  arr.forEach(([s, e], index) => listArr[s].push(e));
  console.log(listArr);

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

    // 현재 current 번호가 방문할 수 있는 노드들을 가지고 있는 배열 listArr[current] 를 connArr 로 선언
    let connArr = listArr[current];

    // connArr 순회
    for (let i = 0; i < connArr.length; i++) {
      // 현재 current 번호가 방문할 수 있는 노드(connArr[i]) 를 확인용 배열 ch 인덱스값으로 넣어 방문 여부확인
      // 이전에 방문하지 않았다면 ch 배열에 방문여부를 업데이트하고 방문할 노드값을 기준으로 DFS 재귀적으로 호출
      if (ch[connArr[i]] === 0) {
        ch[connArr[i]] = 1;
        DFS(connArr[i], [...chkArr, connArr[i]]);

        ch[connArr[i]] = 0; // 재활용을 위한 초기화
      }
    }
  }

  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차원배열 listArr 과 재귀함수 과정에서 방문한 노드들을 확인 하기 위한 체크용 배열 ch 선언
2. 주어진 노드 연결 정보 배열 arr 순회하면서 listArr 를 인접리스트 형식으로 구현
3. 노드들을 순회하며 경로를 점검하기 위해 방문할 노드번호를 의미하는 인자 current, 현재까지 방문한 노드 순서대로 저장한 배열 인자 chkArr 를 가지는 재귀함수 DFS 선언
4. 현재 노드 번호를 의미하는 current 를 기준으로 방문 가능한 노드 번호들의 배열 즉 listArr[current] 를 connArr 변수로 선언
5. connArr 순회하면서 각 노드를 확인용 배열 ch 인덱스값으로 넣어 방문 여부 확인
6. 이전에 방문하지 않았다면 ch 배열에 방문여부를 업데이트하고 방문할 노드 값을 기준으로 DFS 함수를 재귀적으로 호출 이후에 ch 배열을 재활용을 위해 초기화
7. 위 과정을 반복하면서 만약 n 번 노드까지 도착한 경우 함수를 종료하고 정답 1 증가

보완할 수 있는 부분

좀 더 깔끔하게 따로 변수를 쓰지 않고 forof 사용

// 기존코드
let connArr = listArr[current];

for (let i = 0; i < connArr.length; i++) {
    if (ch[connArr[i]] ===  0) {
        ...
    }    
}

// 보완코드
for(let connNode of listArr[current]){
    if (connNode ===  0) {
        ...
    }
}

---

참고

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/dashboard

https://velog.io/@bami/%EC%9D%B8%EC%A0%91-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EA%B7%B8%EB%9E%98%ED%94%84-Adjacent-List-Graph