백준 온라인 저지의 1697번 숨바꼭질 문제입니다.
[링크] https://www.acmicpc.net/problem/1697
문제 조건과 설명
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
Input
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
Output
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
생각한 아이디어
처음에는 DP로 접근을 해볼까 했는데, 바로 떠오르지는 않아서 나중에 다시 생각해보려고 합니다.
다른 방법으로,수빈이의 위치에서 1초 후에 갈 수 있는 모든 좌표를 계산하여 큐에 집어넣고 BFS로 탐색하면 효율적일 것이라는 생각을 했습니다.
단, 가장 빠른 시간을 출력하는 것이므로, 이미 방문했던 위치에서는 다시 그 위치에서 갈 수 있는 좌표를 계산하고, 큐에 넣는 과정을 하면 안 됩니다. 즉, 중복되는 곳은 생략해야 합니다.
수빈이의 시작 위치가 5였을 때, 1초 뒤에 갈 수 있는 곳은 총 3가지입니다.
즉, -1, +1, *2 한 곳으로 갈 수 있으므로 4, 6, 10을 큐에 집어넣습니다.
그리고 BFS 탐색을 진행합니다.
4가 큐의 맨 앞에 있으니 꺼내고, 4에서 갈 수 있는 곳 3가지를 큐에 다시 넣습니다.
이 때, 이미 방문했던 위치는 큐에 넣으면 안 되므로 visit을 판별하는 코드를 작성해야 할 것입니다.
아래 그림을 참조하면 좀 더 이해하기 편하실 것입니다.
이미 방문한 곳을 판별하기 위한 bool type의 visit 배열을 만들었고,
큐에 처음 들어갈 때 그 위치에 도달했을 때 걸린 시간도 같이 넣어주기 위해 pair<int, int> 형 큐를 선언하였습니다. 즉, 그림에서 0초, 1초, 2초, … 등의 숫자를 같이 넣는다는 의미입니다.
예를 들어, 큐에 4, 6, 10이 들어갈 때, {4, 1} , {6, 1}, {10, 1} 이 들어가게 됩니다.
이 숫자를 소스코드에서는 depth로 이름지었습니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
queue<pair<int,int>> q;
bool visit[100001];
int N, K, result;
// 해당 위치가 유효한지 확인하는 함수
bool valid(int n) {
if (n < 0 || n > 100000 || visit[n])
return false;
return true;
}
void bfs(int n) {
while (!q.empty()) {
// 큐에서 꺼내기
int data = q.front().first;
int depth = q.front().second;
q.pop();
// K와 같으면 바로 그 때의 depth를 담고 종료
if (data == K) {
result = depth;
break;
}
// 갈 수 있는 3갈래의 좌표의 유효성을 판단하고 큐에 push
if (valid(data - 1)){
visit[data - 1] = true;
q.push({ data - 1, depth + 1 });
}
if (valid(data + 1)) {
visit[data + 1] = true;
q.push({ data + 1, depth + 1 });
}
if (valid(data * 2)) {
visit[data * 2] = true;
q.push({ data * 2, depth + 1 });
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
q.push({ N, 0 });
visit[N] = true;
bfs(N);
cout << result;
return 0;
}