문제 링크입니다: https://www.acmicpc.net/problem/13549
http://jaimemin.tistory.com/582, http://jaimemin.tistory.com/581과 유사한 문제였습니다.
이번에는 순간이동하는데 0초가 걸리므로 그냥 queue가 아닌 priority queue 즉, 우선순위 큐를 통해 BFS 기법으로 풀어야하는 문제였습니다.
주의할 점은 경과시간을 기준으로 우선순위를 결정해야하며 경과시간이 짧을수록 더 높은 우선순위를 갖게 우선순위 큐를 정의해야한다는 점이였습니다.
따라서, 위와 같은 조건으로 문제를 풀 경우 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; 이렇게 선언해야합니다.
#include <iostream>
#include <vector>
#include <functional>
#include <queue>
using namespace std;
const int MAX = 100000 + 1;
bool visited[MAX];
int minSecond(int N, int K)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
//경과 시간을 기준으로 우선순위 큐(짧을수록 우선순위 크다)
q.push(make_pair(0, N));
visited[N] = true;
while (!q.empty())
{
int curSec = q.top().first;
int curLoc = q.top().second;
q.pop();
if (curLoc == K) //목적지 도달 시 break
return curSec;
//세 가지 경우의 수
//이미 방문한 지점은 큐에 넣지 않는다
if (curLoc * 2 < MAX && !visited[curLoc * 2])
{
q.push(make_pair(curSec, curLoc * 2)); //순간이동하는데 걸리는 시간 0초
visited[curLoc * 2] = true;
}
if (curLoc + 1 < MAX && !visited[curLoc + 1])
{
q.push(make_pair(curSec + 1, curLoc + 1));
visited[curLoc + 1] = true;
}
if (curLoc - 1 >= 0 && !visited[curLoc - 1])
{
q.push(make_pair(curSec + 1, curLoc - 1));
visited[curLoc - 1] = true;
}
}
}
int main(void)
{
int N, K;
cin >> N >> K;
cout << minSecond(N, K) << "\n";
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 11725번 트리의 부모 찾기 (4) | 2018.06.19 |
---|---|
백준 13913번 숨바꼭질 4 (0) | 2018.06.19 |
백준 12851번 숨바꼭질 2 (6) | 2018.06.19 |
백준 1697번 숨바꼭질 (7) | 2018.06.19 |
백준 1966번 프린터 큐 (0) | 2018.06.18 |