[백준/JS] 2644 촌수계산

문제

문제 풀이

촌수를 구하는 문제입니다.
주어진 두 노드 간에 거리를 구하면 되는 문제입니다.

위 그림 처럼 주어진 노드가 7,3인 경우
7에서 출발해 3까지 갈 때 몇번을 거치는지 세어주면 됩니다.

코드로 구현!

DFS로 구현했습니다.
계속해서 타고 들어가고 나오고를 반복해야하기 때문입니다.

  if (cur == b) {
    ans = cnt;
    return;
  }

  for (let i = 0; i < arrList[cur].length; i++) {
    if (visited[arrList[cur][i]]) continue;

    visited[arrList[cur][i]] = true;
    dfs(arrList[cur][i], cnt + 1);
  }
};

• 인자는 현재 노드 값과 cnt 즉 촌수 값을 넣어주었습니다.
• 처음에 바로 현재노드가 내가 찾으려고 하는 노드 인지 확인
  • 현재노드가 내가 찾으려고 하는 노드면 반환과 동시에 정답
• 내가 찾으려고 하는 노드가 아닐 경우에는 나와 이어져 있는 모든 노드를 탐색합니다.
  • 허나 이때 방문 여부를 꼭 체크해주어야 합니다.

잘못 생각한 점

1. 양방향 그래프 이다!

위에서 부터 내려오는 것이라고 생각해서 단방향으로 인접리스트를 짰습니다.

[ 
  [], 
  [ 2, 3 ], 
  [ 7, 8, 9 ], 
  [], 
  [ 5, 6 ], 
  [], 
  [], 
  [], 
  [], 
  [] 
]

이렇게 하니 탐색 코드가 너무 어려워졌습니다.

[
  [],             
  [ 2, 3 ],
  [ 1, 7, 8, 9 ], 
  [ 1 ],
  [ 5, 6 ],       
  [ 4 ],
  [ 4 ],          
  [ 2 ],
  [ 2 ],          
  [ 2 ]
]

이와 같이 변경하여 자신의 노드가 찾으려고 하는 노드가 아니면 자신과 이어져있는 다른 노드를 탐색하도록 했습니다.

2. 방문 여부를 체크해주지 않음

답이 안나오길래 이동 경로를 출력해보니

7에서 2로 이동
2에서 1로 이동
1에서 2로 이동
.
.
.

바로 1과 2가 서로 계속 탐색을 하여 무한루프가 발생했습니다.

따라서 방문 배열을 만들어주고 방문하지 않았을 경우에만 탐색하도록 변경했습니다.

let visited = Array(n + 1).fill(false);

결과 코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./test.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

let n = Number(input.shift());
let [a, b] = input.shift().split(" ").map(Number);
let arrList = Array(n + 1)
  .fill(null)
  .map(() => []);

let arrSize = Number(input.shift());

for (let t = 1; t <= arrSize; t++) {
  let [idx, value] = input.shift().split(" ").map(Number);
  arrList[idx].push(value);
  arrList[value].push(idx);
}

let ans = 0;
let visited = Array(n + 1).fill(false);

const dfs = (cur, cnt) => {
  if (cur == b) {
    ans = cnt;
    return;
  }

  for (let i = 0; i < arrList[cur].length; i++) {
    if (visited[arrList[cur][i]]) continue;

    visited[arrList[cur][i]] = true;
    dfs(arrList[cur][i], cnt + 1);
  }
};

visited[a] = true;
dfs(a, 0);

ans == 0 ? console.log(-1) : console.log(ans);