백준 12851번 숨바꼭질 2

문제 링크입니다: https://www.acmicpc.net/problem/12851

http://jaimemin.tistory.com/581과 비슷한 문제였지만 가장 빠른 시간내에 도착할 수 있는 방법의 가지수까지 출력해야하는 문제였습니다.

숨바꼭질 문제에서는 이미 방문한 지점을 큐에 넣지 않았지만 숨바꼭질 2 문제에서는 방법의 가지수까지 고려해야하므로 큐에서 pop할 때 해당 지점을 방문했다고 표시하는 것이 핵심이였습니다.

예를 들어, N=1 K=4를 입력할 경우,

i) 1->(1+1)->(2*2)

ii) 1->(1*2)->(2*2)

이렇게 총 두가지 방법이 있습니다.

하지만, 숨바꼭질1에서처럼 큐에 집어넣을 때 방문지점을 표시하면 두 번째 경우를 고려하지 않게 되므로 오답이 됩니다.

따라서, 큐에 push할 때가 아닌 pop할 때 방문지점을 표시하면 쉽게 풀 수 있는 문제였습니다!

#include <iostream>

#include <queue>

using namespace std;

 

const int MAX = 100000 + 1;

 

int cnt;

int minSec;

bool visited[MAX];

 

int minSecond(int N, int K)

{

        queue<pair<int, int>> q;

 

        q.push(make_pair(N, 0));

        visited[N] = true;

 

        while (!q.empty())

        {

                 int curLoc = q.front().first;

                 int curSec = q.front().second;

                 q.pop();

 

                 visited[curLoc] = true; //숨바꼭질과 달리 숨바꼭질 2에서는 큐에서 pop할 때 방문지점 표시

 

                 //이미 목적지에 한번 도달했을 경우 cnt++

                 if (minSec && minSec == curSec && curLoc == K)

                         cnt++;

 

                 //최초로 목적지 도달시 최소 시간 기록하고 cnt++

                 if (!minSec && curLoc == K)

                 {

                         minSec = curSec;

                         cnt++;

                 }

 

                 //세 가지 경우의 수

                 if (curLoc + 1 < MAX && !visited[curLoc + 1])

                         q.push(make_pair(curLoc + 1, curSec + 1));

                 if (curLoc - 1 >= 0 && !visited[curLoc - 1])

                         q.push(make_pair(curLoc - 1, curSec + 1));

                 if (curLoc * 2 < MAX && !visited[curLoc * 2])

                         q.push(make_pair(curLoc * 2, curSec + 1));

        }

        return minSec;

}

 

int main(void)

{

        int N, K;

        cin >> N >> K;

 

        cout << minSecond(N, K) << "\n";

        cout << cnt << endl;

 

        return 0;

}

 

 

개발환경:Visual Studio 2017

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