문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
접근 방식
처음엔 1697 번 문제에서 달라진 점은 2*X의 위치로 이동할 때 초를 세지 않는다는 점 밖에 없어서
단순 BFS 풀이에서 if 조건문을 추가하여
2*X 일때만 dist 배열 값을 이전 값과 똑같이 적용해 주었다
근데 계속 런타임 에러 (OutOfBouds) 에러가 나길래 구글에서 찾아보았더니
2*X 으로 순간이동 할 때는 우선순위를 더 높게 저장해주어야 한다고 했다
즉, 0-1 BFS 로 풀어야 하는 문제였던 것이다.
0-1 BFS 를 잠깐 설명하자면 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 사용할 수 있다
이때, 시간복잡도가 O(V+E)이므로 보편적으로 사용하는 다익스트라 알고리즘의 시간복잡보다 선형 시간 복잡도로
문제를 해결할 수 있다는 장점이 있다!
C++에서는 deque 를 STL로 제공해주기 때문에 이를 사용해서 쉽게 풀 수 있었다.
2*X로 이동할 때는 deque에 앞으로 삽입해주고
X-1, X+1로 이동할 때는 뒤로 삽입해준다
또한, 이때 X-1보다 X+1을 먼저 실행한다면
4 -> 3 -> 6
4 -> 5 -> 6
으로 오답이 출력되므로 주의해야 한다
소스코드
#include<bits/stdc++.h>
using namespace std;
int dist[200002];
deque<int> q;
int MX = 200000;
int main() {
int N,K; cin>>N>>K;
fill(dist, dist+200000, -1);
q.push_back(N);
dist[N] = 0;
while(!q.empty()) {
int x = q.front(); q.pop_front();
if(2*x < MX && dist[2*x] == -1) {
dist[2*x] = dist[x];
q.push_front(2*x);
}
for(auto nxt : { x-1, x+1}) {
if(dist[nxt] != -1) continue;
if(nxt < 0 || nxt > MX) continue;
dist[nxt] = dist[x]+1;
q.push_back(nxt);
}
}
cout<<dist[K];
}
'Algorithm' 카테고리의 다른 글
[BOJ] 요세푸스 문제 1158번 C++ (1) | 2024.01.13 |
---|---|
[BOJ] 에디터 1406번 C++ (1) | 2024.01.09 |
[BOJ] 스타트와 링크 14889번 C++ (1) | 2023.12.19 |
[BOJ] 여우는 어떻게 울지? 9536번 C++ (0) | 2023.12.13 |
[BOJ] 쿼드트리 1992번 c++ (0) | 2023.08.02 |