백준 13549번 숨바꼭질 3

문제 링크입니다: 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

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~