이번에는 백준 17071번 숨바꼭질 5 문제를 풀어보았습니다.
처음에는 일반적인 숨바꼭질 문제처럼 BFS를 수행하면 될 것이라고 생각했습니다.
하지만 이번 문제는 동생도 계속 이동한다는 점이 기존 문제와 달랐습니다.
특히 동생은 매 초마다 이동 거리가 1씩 증가하기 때문에 위치가 계속 바뀌게 됩니다.
처음에는 수빈이가 특정 위치에 더 빨리 도착할 수 있다면 동생이 나중에 그 위치에 왔을 때 만날 수 있을 것이라고 생각했습니다.
하지만 단순히 시간 차이가 짝수인지 홀수인지만 확인하는 방식으로는 해결되지 않았습니다.
같은 위치라도 짝수 시간에 도착 가능한 경우와 홀수 시간에 도착 가능한 경우가 서로 다를 수 있기 때문입니다.
그래서 방문 배열을 시간의 홀짝에 따라 나누어 관리하는 방식으로 구현하였습니다.
문제 설명
수빈이는 현재 위치 N에 있고 동생은 K에 있습니다.
수빈이는 다음 세 가지 방법으로 이동할 수 있습니다.
- X - 1
- X + 1
- X * 2
동생은 매 초마다 이동하며 이동 거리가 계속 증가합니다.
0초 : K
1초 : K + 1
2초 : K + 1 + 2
3초 : K + 1 + 2 + 3수빈이가 동생을 가장 빠르게 만나는 시간을 구하는 문제입니다.
풀이 아이디어
동생의 위치는 시간에 따라 계속 변합니다.
시간이 t일 때 동생의 위치는 다음과 같습니다.
K + 1 + 2 + ... + t즉,
K + t(t+1)/2위치에 존재하게 됩니다.
문제는 수빈이가 특정 위치에 더 빨리 도착했다고 해서 반드시 동생을 만날 수 있는 것이 아니라는 점입니다.
예를 들어 어떤 위치에 수빈이가 짝수 시간에만 도착 가능하다면, 동생이 홀수 시간에 그 위치에 왔을 때는 만날 수 없습니다.
그래서 방문 배열을 다음과 같이 분리하였습니다.
visited[2][500001]- visited[0] : 짝수 시간에 방문 가능한 위치
- visited[1] : 홀수 시간에 방문 가능한 위치
BFS를 진행하면서 현재 시간의 홀짝에 맞는 방문 배열에 저장하였고, 동생의 위치 역시 현재 시간의 홀짝에 맞는 배열을 확인하여 만날 수 있는지 판단하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int visited[2][500001];
int bro, subin;
int main() {
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
cin >> subin >> bro;
if (subin == bro) {
cout << 0;
return 0;
}
queue<int> q;
q.push(subin);
visited[0][subin] = 1;
int t=0;
while(!q.empty()) {
int qsize = q.size();
int brother_pos = t*(t+1)/2 + bro;
if (brother_pos > 500000)
break;
if (visited[t%2][brother_pos]) {
cout << t;
return 0;
}
while(qsize--) {
int curr = q.front();
q.pop();
for (int next : {curr-1, curr+1, curr*2}) {
if (next < 0 || next > 500000) continue;
if (visited[(t+1)%2][next]) continue;
visited[(t+1)%2][next] = 1;
q.push(next);
}
}
t++;
}
cout << -1;
return 0;
}풀이 흐름
- 수빈이 위치를 시작점으로 BFS를 수행합니다.
- 현재 시간 t에서 동생의 위치를 계산합니다.
- 현재 시간의 홀짝에 해당하는 방문 배열에서 동생 위치 방문 여부를 확인합니다.
- 만날 수 있다면 현재 시간을 출력합니다.
- 아니라면 수빈이가 이동 가능한 위치를 다음 시간 배열에 저장합니다.
- BFS를 계속 진행합니다.
- 동생 위치가 500000을 넘어가거나 더 이상 만날 수 없는 경우 -1을 출력합니다.
구현 포인트
1. 동생 위치 계산
시간이 t일 때 동생의 위치를 계산하였습니다.
int brother_pos = t*(t+1)/2 + bro;동생은 매 초마다 이동 거리가 1씩 증가하기 때문에 누적합 공식을 이용하였습니다.
2. 방문 배열을 두 개로 분리
이 문제의 핵심이었던 부분입니다.
int visited[2][500001];위치를 방문했는지만 저장하는 것이 아니라, 해당 위치를 짝수 시간에 방문했는지 홀수 시간에 방문했는지를 구분하여 저장하였습니다.
3. 현재 시간의 홀짝 확인
현재 시간이 짝수인지 홀수인지에 따라 다른 방문 배열을 확인하였습니다.
if (visited[t%2][brother_pos]) {
cout << t;
return 0;
}현재 시간에 동생 위치에 도달 가능한 경우 바로 정답을 출력하였습니다.
4. 다음 시간 배열에 저장
현재 시간 t에서 이동한 위치들은 모두 시간 t+1에 도착하는 위치들입니다.
그래서 다음과 같이 저장하였습니다.
visited[(t+1)%2][next] = 1;현재 시간과 다음 시간의 방문 정보를 분리하여 관리할 수 있었습니다.
5. BFS 레벨 단위 탐색
현재 시간에 도달 가능한 위치들을 한 번에 처리하기 위해 큐의 크기를 먼저 저장하였습니다.
int qsize = q.size();현재 레벨의 모든 위치를 처리한 뒤 시간을 1 증가시켰습니다.
t++;이렇게 하면 BFS의 레벨이 곧 시간이 되도록 구현할 수 있었습니다.
