[백준/Node.js] 17071 숨바꼭질 5

 

---

문제 접근

이 문제는 BFS와 시간에 따른 위치 변화를 동시에 고려해야 하는 문제이다. 수빈이가 매초 이동할 수 있는 경로를 BFS 방식으로 탐색하면서, 동생이 매초 가속하는 위치에 도달할 수 있는지 체크해야 한다. 하지만 단순 BFS로는 문제가 풀리지 않는다.

 

수빈이의 이동:

- 매초 X-1, X+1, X*2로 이동할 수 있다. => BFS로 탐색하며 매초 어디로 이동할 수 있는지 추적

 

동생의 이동

- 매초 가속하며 이동한다. => t초 후의 위치는 K + t(t+1)/2

 

짝수/홀수 시간 체크:

수빈이와 동생이 같은 시간에 같은 위치에 있어야만 만날 수 있다. 다시 말해, 수빈이가 어떤 위치에 도착하는 시간이 짝수 시간인지, 홀수 시간인지에 따라 그 시간에 동생이 있는 위치가 다르다.

 

ex) 수빈이와 동생이 서로 다른 시간에 같은 위치에 있을 수 있지만, 시간 차이로 인해 만나지 못하는 경우

t초 후	수빈이의 위치	동생의 위치	만남?
0	5	17	X
1	[4, 6, 10]	18	X
2	[3, 5, 9, 11, 12]	20	X
3	[2, 4, 10, 12, 20]	23	X

3초 후에 수빈이가 20에 도착했지만, 동생은 23에 있기 때문에 만나지 못한다. 

 

수빈이는 매초마다 -1, +1, 2배 이동이 가능하므로, 특정 위치에 도달했다가 그 위치로 다시 돌아오는 일이 가능하다. 예를 들어, 수빈이가 14초에 x 지점에 도달했다면, 15초에 x-1, 16초에는 다시 x로 돌아올 수 있다. 즉, 짝수 시간에 어떤 위치에 있었다면, 이후에도 짝수 시간마다 그 위치에 도달할 수 있다. 마찬가지로 홀수 시간에 도달한 위치라면 이후에도 홀수 시간마다 다시 그 위치에 도달할 수 있다. 따라서 짝수/홀수를 나누어서 관리해야 한다. 

 

 

 

탐색 종료 조건:

- 만났을 경우: 수빈이가 해당 시간에 해당 위치에 도달할 수 있는지를 확인한다. 즉, 수빈이가 visited[K + t(t+1) / 2][time % 2]에서 동생을 만나면 그 시간을 바로 출력한다.

- 동생이 500,000을 넘는 순간은 더 이상 탐색할 필요가 없으므로 탐색을 종료한다. 

 

---

풀이

 

const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const [N, K] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const MAX = 500000;
const visited = Array.from({ length: MAX + 1 }, () => Array(2).fill(false));

 

• N과 K는 수빈이와 동생의 초기 위치
• MAX는 500,000으로 설정하여 범위 내에서만 탐색
• visited 배열은 짝수 시간과 홀수 시간을 구분하여 수빈이가 해당 위치에 도달했는지를 기록

function bfs(start) {
  let queue = [];
  let time = 0;
  queue.push([start, 0]); // 시작 위치와 초기 시간 0초
  visited[start][0] = true; // 0초에 시작 위치에 방문

  while (queue.length) {
    const KPos = K + (time * (time + 1)) / 2; // t초 후 동생의 위치
    if (KPos > MAX) return -1; // 동생이 범위를 넘으면 종료
    if (visited[KPos][time % 2]) return time; // 수빈이가 동생을 만난 경우

    // 현재 큐에 있는 모든 상태 탐색
    for (let i = 0; i < queue.length; i++) {
      const [cur, curTime] = queue.shift();
      const nextTime = curTime + 1;
      const parity = nextTime % 2;

      for (let next of [cur + 1, cur - 1, cur * 2]) {
        if (next >= 0 && next <= MAX && !visited[next][parity]) {
          visited[next][parity] = true;
          queue.push([next, nextTime]);
        }
      }
    }

    time++;
  }

  return -1;
}

// 처음에 수빈이와 동생이 같은 위치면 0 출력, 아니면 bfs 탐색 시작
console.log(N === K ? 0 : bfs(N));

 

BFS에서는 같은 시간대(초 단위)에서 이동할 수 있는 모든 상태를 먼저 처리하고, 그 다음에 한 번의 시간이 지난 후에 새로운 상태를 처리한다. 현재 큐에 있는 상태들을 먼저 모두 처리하면, 다음 초에 발생하는 상태들은 그 다음 단계에서 처리하게 되므로, 시간 단위를 명확히 관리했다.

 

 

이 문제에서의 BFS는 최대 탐색 범위가 500,000이며, 각 위치에서 최대 3번 이동할 수 있다. 이때 BFS에서는 모든 경로를 중복 없이 탐색하기 때문에 시간 복잡도는 탐색해야 하는 노드의 수에 의해 결정되며, 이는 MAX 값을 넘지 않는다. 따라서 시간 복잡도는 O(MAX)이다. 이 정도는 충분히 제한 시간 내에 해결 가능한 범위이다.