백준 13549번 C++ 풀이
https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
| 시간 제한 | 메모리 제한 | solved.ac 티어 |
| 2초 | 512MB | 골드 5 |
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
저번 숨바꼭질 문제는(https://codejin.tistory.com/212) 모든 간선의 가중치가 1로 모두 같았기 때문에 단순한 bfs로 풀 수 있는 문제였다. 하지만 이번에는 2*x의 위치로 이동하는 경우의 가중치가 0으로, x ± 1로 이동할때의 가중치인 1과는 다르다. 따라서 이 문제는 단순한 bfs로 풀 수 없다. 만약 저번 숨바꼭질 문제 코드를 그대로 사용한다면, 당장 반례 케이스가 4 6이다. 입력으로 4 6이 들어온다면, 단순한 bfs의 경우 경로를 {4, 5, 6}으로 총 2초가 걸린다고 판단하고 2를 출력하게 된다. 하지만, {4, 3, 6}으로 이동한다면 1초가 걸린다.
따라서 이 문제는 최단 경로 알고리즘을 사용하는 것이 알맞을 것 같았다. 간선의 가중치가 모두 0 이상이기 때문에 다익스트라 알고리즘을 사용했다.
#include <bits/stdc++.h>
#define INF (int)1e9
#define LEN ((int)1e5 + 5)
using namespace std;
using pii = pair<int, int>;
void sol(int n, int k) {
make_graph();
int dist_arr[2 * LEN];
fill(dist_arr, dist_arr + 2 * LEN, INF);
bool visit[2 * LEN] = { false };
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({ 0, n });
dist_arr[n] = 0;
while(!pq.empty()) {
pii cur = pq.top();
pq.pop();
if (visit[cur.second]) continue;
visit[cur.second] = true;
if (cur.second <= k && dist_arr[cur.second * 2] > cur.first) {
dist_arr[cur.second * 2] = cur.first;
pq.push({dist_arr[cur.second * 2], cur.second * 2});
}
if (cur.second <= 2 * k && dist_arr[cur.second + 1] > cur.first + 1) {
dist_arr[cur.second + 1] = cur.first + 1;
pq.push({dist_arr[cur.second + 1], cur.second + 1});
}
if (cur.second > 0 && dist_arr[cur.second - 1] > cur.first + 1) {
dist_arr[cur.second - 1] = cur.first + 1;
pq.push({dist_arr[cur.second - 1], cur.second - 1});
}
}
cout << dist_arr[k] << endl;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
sol(n, k);
}
이후 이 문제를 풀어보고 조금 더 알아보고나니, 이런 경우에 다익스트라보다 더 최적화된 알고리즘이 존재하는 것을 알았다. 0-1 bfs 알고리즘이다. 기존의 bfs알고리즘은 간선의 가중치가 모두 같은 경우에 사용할 수 있었다. 하지만, 이 0-1 bfs 알고리즘은 간선의 가중치가 모두 0 또는 1인 그래프에서 최단경로를 구할 때 효율적으로 사용할 수 있다. 단순히 큐를 사용하던 bfs와는 다르게, 덱을 사용하여 가중치가 0일때는 front에, 1일때는 back에 push하고, 나머지는 bfs와 동일하게 작동한다.
#include <bits/stdc++.h>
#define INF (int)1e9
#define LEN ((int)1e5 + 5)
using namespace std;
using pii = pair<int, int>;
void sol(int n, int k) {
deque<int> dq;
int dist_arr[2 * LEN];
fill(dist_arr, dist_arr + 2 * LEN, INF);
bool visit[2 * LEN] = { false };
dq.push_front(n);
dist_arr[n] = 0;
while(!dq.empty()) {
int cur = dq.front();
dq.pop_front();
if (visit[cur]) continue;
visit[cur] = true;
if (cur <= k && dist_arr[cur * 2] > dist_arr[cur]) {
dist_arr[cur * 2] = dist_arr[cur];
dq.push_front(cur * 2);
}
if (cur <= 2 * k && dist_arr[cur + 1] > dist_arr[cur] + 1) {
dist_arr[cur + 1] = dist_arr[cur] + 1;
dq.push_back(cur + 1);
}
if (cur > 0 && dist_arr[cur - 1] > dist_arr[cur] + 1) {
dist_arr[cur - 1] = dist_arr[cur] + 1;
dq.push_back(cur - 1);
}
}
cout << dist_arr[k];
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
sol(n, k);
}
