문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
풀이
순간이동은 비용이 0, 걷기는 비용이 1이므로 일반 BFS보다 0-1 BFS가 더 잘 맞는다. 가중치가 0 또는 1뿐인 그래프에서는 덱을 이용해 최단 거리를 구할 수 있다.
코드에서는 순간이동 결과는 덱의 앞쪽에 넣고, 걷기 연산은 뒤쪽에 넣는다. 이렇게 하면 항상 현재까지 비용이 가장 작은 상태부터 처리되는 효과를 낼 수 있다.
다익스트라를 더 단순한 형태로 압축한 문제가 0-1 BFS다.
코드
//0-1 너비우선탐색
//가중치가 0이라면 덱 앞쪽으로 삽입, 1이라면 덱 뒤쪽으로 삽입
#include <iostream>
#include <deque>
using namespace std;
const int MAX_N = 100000;
bool visit[MAX_N + 1];
void solve() {
deque<pair<int, int>> dq;
int n, k;
cin >> n >> k;
dq.push_back({0, n});
while(!dq.empty()) {
int time = dq.front().first;
int X = dq.front().second;
dq.pop_front();
visit[X] = true;
if (X == k) {
cout << time << '\n';
break;
}
if (X + 1 <= MAX_N && !visit[X + 1])
dq.push_back({time + 1, X + 1});
if (X - 1 >= 0 && !visit[X - 1])
dq.push_back({time + 1, X - 1});
if (X * 2 <= MAX_N && !visit[X * 2])
dq.push_front({time, X * 2});
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도: 위치 범위의 각 상태를 0-1 BFS로 처리하므로 최대 좌표를 이라 할 때 이다.
- 공간 복잡도: 방문 배열과 덱을 사용하므로 이다.
마무리
순간이동이 공짜라는 점 때문에 일반 BFS와는 조금 다르다. 0과 1만 있는 비용이라면 덱 하나로 최단 거리를 처리할 수 있다.
