알고리즘 :: 백준 :: BFS :: 1697 :: 숨바꼭질 (velog.io) 문제의 연장입니다.
1697번
풀이에서 순간이동에 대한 코드에서 push()
할 때 시간을 더해주지 않는 것으로 바꾸기만 하면 AC를 받을 수 있습니다.0
입니다. x
라고 할지라도, 가중치 1
로 온 것과 가중치 0
으로 온 것은 다르므로 서로 다른 점이라고 판단해야 합니다.x
와 0초 소요해서 도착한 x
를 기존의 queue
로는 구분할 수 없기 때문입니다.queue
와 가중치 1에 대한 queue
2개를 사용해야 하는 문제입니다.deque
이라는 자료구조가 queue
를 앞뒤로 합쳐놓은 형태의 자료구조임을 알고있습니다.deque
자료구조를 사용해서 가중치가 0일 때는 push_front()
를, 가중치가 1일 때는 push_back()
을 하는 방식으로 풀이합니다.deque
의 앞쪽에는 가중치가 0인 행동들이 들어가므로 가장 먼지 목표지점 K
에 도착하면 loop를 탈출해도 됩니다.queue
가 아닌 deque
을 사용해야한다는 점을 배울 수 있습니다.#include <iostream>
#include <deque>
#define MAX 100001
using namespace std;
int N, K;
bool visited[MAX];
int solve() {
deque<pair<int,int>> q;
q.push_front({N, 0});
while(!q.empty()){
int pos = q.front().first, t = q.front().second;
if(pos == K) return t;
int goPos = pos + 1, backPos = pos - 1, telePos = 2 * pos;
q.pop_front();
if(telePos < MAX && !visited[telePos]) // 순간이동
visited[telePos] = true, q.push_front({telePos, t});
if(backPos >= 0 && !visited[backPos]) // 한 칸 뒤로 이동
visited[backPos] = true, q.push_back({backPos, t + 1});
if(goPos < MAX && !visited[goPos]) // 한 칸 앞으로 이동
visited[goPos] = true, q.push_back({goPos, t + 1});
}
}
int main(){
cin >> N >> K;
cout << solve() << '\n';
}