문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
풀이
현재 위치에서 갈 수 있는 다음 상태는 x - 1, x + 1, 2x 세 가지뿐이고, 모든 이동 비용이 1로 같다. 그래서 BFS로 처음 도착한 순간이 곧 최소 시간이라는 성질을 그대로 사용할 수 있다.
코드는 위치 배열과 방문 배열을 두고 큐에서 하나씩 꺼내며 다음 위치를 확장한다. 범위를 벗어난 위치만 걸러 주면, 먼저 K에 도달하는 경로가 정답이 된다.
코드
#include <iostream>
#include <queue>
using namespace std;
int N, K, answer;
bool visit[100001];
queue<pair<int, int>> q;
void solve() {
while (!q.empty()) {
int data = q.front().first;
int count = q.front().second;
q.pop();
if (data == K) {
answer = count;
break;
}
if (data + 1 >= 0 && data + 1 < 100001 && !visit[data + 1] ) {
visit[data + 1] = true;
q.push({ data + 1, count + 1 });
}
if (data - 1 >= 0 && data - 1 < 100001 && !visit[data - 1]) {
visit[data - 1] = true;
q.push({ data - 1, count + 1 });
}
if (data * 2 >= 0 && data * 2 < 100001 && !visit[data * 2]) {
visit[data * 2] = true;
q.push({ data * 2, count + 1 });
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> K;
q.push({ N , 0 });
solve();
cout << answer << '\n';
return 0;
}복잡도
- 시간 복잡도: 좌표 범위의 상태를 BFS로 처리하므로 최대 좌표를 이라 할 때 이다.
- 공간 복잡도: 방문 배열과 큐를 사용하므로 이다.
마무리
이동 비용이 모두 1인 상태 공간에서는 처음 도착한 시간이 최단 시간이다. 세 가지 이동만 차례로 확장하면 BFS가 수빈이의 최소 이동 횟수를 바로 찾아 준다.
