숨바꼭질 | JavaScript

September 19, 2023

BFS백준

문제

이번 문제를 간단히 요약하면, 수빈이는 N번째 점에 있고, 동생이 K번째 점에 있는데, 수빈이가 동생을 잡을 수 있는 가장 빠른 초를 구하는 문제였습니다. 수빈이는 1초마다 한번씩 움직일 수 있는데, 한번 움직일 때 자신의 위치에서 +1, -1, *2만큼 움직일 수 있습니다.

풀이

이 문제 풀이의 아이디어를 다음 그래프와 같습니다.

그래프

5번 위치에서 1초동안 4, 6, 10으로 이동할 수 있습니다. -> 4번 위치에서 1초동안 3, 5, 8 위치로 이동할 수 있습니다. 하지만 5번 위치는 이미 방문한 적이 있습니다.

위의 로직대로 그래프를 그려주니, 아래 노드로 이동하기 위해선 1초라는 동일한 가중치를 갖는 최단경로 문제이기 때문에 BFS 문제라고 판단했습니다.

걸리는 시간, 즉 시작노드에서 i번노드까지 가려면 얼마나 걸리는지 초를 어떻게 저장해야할지 고민했는데, visited 배열을 선언해 i번째에 저장했습니다.

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
 
const [n, k] = input[0].split(' ').map(Number);
 
const visited = new Array(100001).fill(0);
 
function bfs(start) {
  // 시작점과 찾아야하는 곳과 같다면 함수를 종료
  if (start === k) return;
 
  const queue = [start];
 
  while (queue.length !== 0) {
    const current = queue.shift();
 
    // 움직일 수 있는 방향을 모두 탐색
    for (let next of [current + 1, current - 1, current * 2]) {
      // 경로를 벗어나는 경우, pass
      if (next < 0 || next > 100000) continue;
      // 이미 방문한 경우, pass
      if (visited[next] !== 0) continue;
 
      // 그렇지 않다면, 탐색
      if (visited[next] === 0) {
        visited[next] = visited[current] + 1;
        queue.push(next);
      }
    }
  }
}
 
bfs(n);
console.log(visited[k]);