BOJ 1697. 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2 * X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
1. 문제 해석
- 수빈이의 위치:N
- 동생의 위치:K
- 동생을 찾는 가장 빠른 시간을 구하는 문제
- 수빈이가 할 수 있는 행동 (위치:X)
1) 걷기: X+1 또는 X-1로 이동 (1초)
2) 순간이동: 2*X로 이동 (1초)
이 문제를 그래프의 문제로 변형하기 위해서는 무엇이 정점이고, 무엇이 간선이 될지 대응해보아야 한다. 먼저, 직관적으로 수빈이와 동생의 위치를 정점으로 생각할 수 있다. 그리고 위치와 위치를 이어주는 간선은 수빈이가 할 수 있는 행동(이동) 이 된다.
수빈이의 위치가 5, 동생의 위치가 17인 경우에 5-10-9-18-17로 4초 만에 동생을 찾을 수 있다.
2. 문제 풀이
- 큐에 수빈이의 위치를 넣어가면서 이동시킨다.
- 한 번 방문한 곳은 다시 방문하지 않는 것이 좋기 때문에, 따로 배열에 체크하면서 방문
•check[i] = i를 방문했는지
•dist[i] = i를 몇 번만에 방문했는지(초)
now->next를 갔다고 한다면
if (check[next] == false) { // 방문하지 않았다면
q.push(next); // 큐에 넣고
check[next] = true; // 방문 표시
dist[next] = dist[now] + 1; // now까지 누적된 값을 next에 더함
}아래의 그림은 N=5, M=17일때 BFS로 탐색하는 과정을 나타낸다. x-1, x+1, 2*x를 동시에 방문하면서 점점 뻗어나가는 모습을 볼 수 있다. 이렇게 BFS로 dist배열의 값을 모두 채워놓으면 M에 해당하는 인덱스의 값이 최소의 시간이 된다.
BFS로 구현한 코드
#include <iostream>
#include <queue>
using namespace std;
const int MAX = 200000;
bool check[MAX+1];
int dist[MAX+1];
int main() {
int n, m;
cin >> n >> m;
check[n] = true; // 시작점(수빈이의 위치) 방문 체크
dist[n] = 0; // 누적 시간은 0초
queue<int> q;
q.push(n);
while (!q.empty()) {
int now = q.front();
q.pop();
if (now-1 >= 0) { // x-1 범위 체크
if (check[now-1] == false) { // 방문 체크
q.push(now-1);
check[now-1] = true;
dist[now-1] = dist[now] + 1; // 1초만큼 더함
}
}
if (now+1 < MAX) { // x+1 범위 체크
if (check[now+1] == false) { // 방문 체크
q.push(now+1);
check[now+1] = true;
dist[now+1] = dist[now] + 1; // 1초만큼 더함
}
}
if (now*2 < MAX) { // 2*x 범위 체크
if (check[now*2] == false) { // 방문 체크
q.push(now*2);
check[now*2] = true;
dist[now*2] = dist[now] + 1; // 1초만큼 더함
}
}
}
cout << dist[m] << '\n';
return 0;
}이때 while문 안에 if문의 순서는 바뀌어도 상관없다. 왜냐하면 어차피 모두 큐에 넣어서 동시에 방문되며, 방문되었다면 그 dist값이 무조건 최소이므로 한번만 방문하면 된다.
그런데 여기서 check배열은 굳이 사용할 필요가 없다. 왜냐하면 dist배열에 값이 없다면 방문하지 않은 것과 같기 때문에 check배열의 역할을 할 수 있기 때문이다. 즉, dist배열의 값으로도 충분히 방문여부를 판단할 수 있다. 단, 처음 시작점에서 0으로 시작하므로 -1로 초기화 해준다.
check배열 제거한 코드
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAX = 200000;
int dist[MAX+1];
int main() {
int n, m;
cin >> n >> m;
memset(dist, -1, sizeof(dist)); // dist배열을 -1로 초기화
dist[n] = 0;
queue<int> q;
q.push(n);
while (!q.empty()) {
int now = q.front();
q.pop();
if (now*2 < MAX) {
if (dist[now*2] == -1) {
q.push(now*2);
dist[now*2] = dist[now] + 1;
}
}
if (now+1 < MAX) {
if (dist[now+1] == -1) {
q.push(now+1);
dist[now+1] = dist[now] + 1;
}
}
if (now-1 >= 0) {
if (dist[now-1] == -1) {
q.push(now-1);
dist[now-1] = dist[now] + 1;
}
}
}
cout << dist[m] << '\n';
return 0;
}