[문제]
https://www.acmicpc.net/problem/13549
[문제 풀이]
우선순위큐를 이용해서 문제를 풀었었다.
문제에서 *2배를 할 경우에는 시간이 지나지 않는다고 했으니 우선순위큐를 pair로 만든 뒤에 시간을 기준으로 정렬을 하자.
*우선순위 큐에서 제일 앞에 있는(시간이 0부터 적은 위치)가 하나씩 빠지니 목표에 도착하는 순간 가장 작은 값이 나온다. 문제를 풀다가 전부 가야한다고 헷갈려서 해당 조건을 빼니 10%에서 계속 틀렸습니다가 발생하였다.
*현재 코드는 헷갈려서 보기가 어려운 부분이 있다. 가독성이 좋게 나중에 고치도록 하자.
[코드]
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int visited[200001];
int brother[200001];
int n,k;
int answer = 99999;
//0초 이동이 언제나 가장 빠르게 선행되어야 한다.
struct compare{
bool operator()(pair<int ,int> a, pair<int, int> b){
return a.second > b.second;
}
};
void bfs(){
priority_queue<pair<int, int>, vector<pair<int, int> >, compare > subin;
subin.push(make_pair(n,0) );
visited[n] = 1;
brother[n] = 1;
while(subin.size() > 0){
int curX = subin.top().first;
int curT = subin.top().second;
subin.pop();
if(curX == k){
answer = curT;
return;
}
if(curX + 1 <= 100000){
//1. 방문을 하지 않았을 경우
//2. 방문을 하였지만 방문했었을때보다 현재 경우가 더 작은 경우.
if(visited[curX + 1] == 0){
visited[curX + 1] = 1;
brother[curX + 1] = curT + 1;
subin.push(make_pair(curX + 1, curT + 1));
}
else if(visited[curX + 1] == 1){
if(brother[curX + 1] > curT + 1){
brother[curX + 1] = curT + 1;
subin.push(make_pair(curX + 1, curT + 1));
}
}
}
if(curX - 1 >= 0){
if(visited[curX - 1] == 0){
visited[curX - 1 ] = 1;
brother[curX - 1] = curT + 1;
subin.push(make_pair(curX - 1 , curT + 1));
}
else if(visited[curX - 1] == 1){
if(brother[curX - 1] > curT + 1){
brother[curX - 1] = curT + 1;
subin.push(make_pair(curX - 1, curT + 1));
}
}
}
if(curX * 2 <= 100000){
if(visited[curX * 2] == 0){
visited[curX * 2] = 1;
brother[curX * 2] = curT;
subin.push(make_pair(curX * 2, curT));
}
else if(visited[curX * 2] == 1){
if(brother[curX * 2] > curT){
brother[curX * 2] = curT;
subin.push(make_pair(curX * 2, curT));
}
}
}
}
return;
}
int main(){
cin>>n>>k;
bfs();
cout<<answer<<endl;
return 0;
}