문제 이해
- 수빈이는 동생과 숨바꼭질을 하고 있다.
- 수빈이는 현재 점 N에 위치해있고, 동생은 K에 위치해있다.
- 수빈이의 위치가 X일 때, 수진이는 1초 후에 X+1 or X-1로 걷거나 0초 후에 2*X 위치로 순간이동 할 수 있다.
- 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하여라
<입력>
- N: 수빈이의 위치 (0 ~ 100,000, 10^5)
- K: 동생의 위치 (0 ~ 100,000, 10^5)
<출력>
- 수빈이가 동생의 위치까지 도달하는 가장 빠른 시간을 출력하라.
<조건>
- 시간 제한: 2초
- 메모리 제한: 512MB
문제 풀이(BFS)
처음에 이 문제에 접근할 때는 우선순위 큐와 BFS를 활용해서 풀어보려 했다.
<전체 코드>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin>>n>>k;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, n});
while(!pq.empty()){
int cost = pq.top().first;
int now = pq.top().second;
pq.pop();
if(now == k){
cout<<cost;
break;
}
if(now < 0 || now > 1e5) continue;
pq.push({cost, 2 * now});
pq.push({cost+1, now + 1});
pq.push({cost+1, now - 1});
}
return 0;
}다음과 같은 코드였는데
시간 초과로 AC를 받지 못했다.
시간을 단축할 방법을 생각해보니
이미 방문한 지점에는 다시 방문할 필요가 없다는 걸 깨달았다.
그래서 bool형 배열을 하나 선언해 방문한 지점은 방문하지 않는 코드로 수정하였더니 AC를 받을 수 있었다.
<전체 코드>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
bool visited[101010];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin>>n>>k;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, n});
while(!pq.empty()){
int cost = pq.top().first;
int now = pq.top().second;
pq.pop();
if(now == k){
cout<<cost;
break;
}
if(visited[now]) continue;
visited[now] = true;
if(2 * now <= 1e5) pq.push({cost, 2 * now});
if(now + 1 <= 1e5) pq.push({cost+1, now + 1});
if(now - 1 >= 0) pq.push({cost+1, now - 1});
}
return 0;
}<배열의 크기에 대한 고찰>
배열의 크기를 2 * 100,000보다 크게 해야된다는 포스트도 있었지만
N: 50,001, K: 100,000일때를 가정해보면
50,001 -> 100,002 -> 100,001 -> 100,000보다
50,001 -> 50,000 -> 100,000이 더 효율적이다.
50,001보다 더 큰 경우도 마찬가지이다.
수빈이가 (-)로 이동할 수 있는 건 1초에 1만큼이기에,
최대값을 초과했다가 돌아오는 것보다 최댓값 안에서 이동하는 편이 효율적인 것이다.
고로, 큐에 넣을 때 조건을 100,000보다 작을 때만 넣게하여 초과하는 경우는 배재하였다.
물론 배열의 크기를 200,000보다 크게 하는 편이 더 마음 편한건 사실이긴 하다.
문제 풀이(0-1 BFS)
그런데 위의 풀이보다 더 시간복잡도 측면에서 효율적인 방법이 있었음을
인터넷 서치를 통해 발견할 수 있었다.
이 방법은 가중치가 0과 1로만 구성되어 있어야 가능한 방법이다.
deque를 통해 구현하는데,
가중치가 0인 경우는 앞에 넣고,
가중치가 1인 경우는 뒤에 넣어서, 우선 순위를 맞춰주는 것이다.
<전체 코드>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int dist[202020];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin>>n>>k;
fill(dist, dist + 202020, 987654321);
deque <int> dq;
dq.push_front(n);
dist[n] = 0;
while(!dq.empty()){
int now = dq.front();
dq.pop_front();
if(now == k){
cout<< dist[k];
break;
}
if(now * 2 <= 200000 && dist[now] < dist[now * 2]){
dist[now * 2] = dist[now];
dq.push_front(now * 2);
}if(now - 1 >= 0 && dist[now] + 1 < dist[now-1]){
dist[now-1] = dist[now] + 1;
dq.push_back(now-1);
}if(now + 1 <= 200000 && dist[now] + 1 < dist[now+1]){
dist[now+1] = dist[now] + 1;
dq.push_back(now+1);
}
}
return 0;
}0-1 BFS 알고리즘에 대해 접할 수 있었던 문제였다! 앞으로 0-1 BFS에 대해서 더 알아볼 예정이다.!!
또한, 한 문제에도 풀이가 정말 다양하고, 각 방법에도 코드의 스타일이 다양했다.문제를 풀 때 좋은 방법에 대해 잘 숙지하는 것의 중요성을 배울 수 있었던 문제였기도 했다.