[BOJ] #12851 숨바꼭질 2

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

---

#1697 숨바꼭질의 연장선상에 있는 문제이다. 숨바꼭질 3는 아예 다익스트라로 노선을 변경해서 풀면 그나마 풀어냈었는데, 2는 오히려 같은 BFS 코드를 공유하는 문제인지라, 방법을 생각해내는것에 더 어려움을 겪었다. 일단 문제 자체는 가중치가 없는 그래프를 탐색하여 최단거리를 도출해야 하기 때문에 BFS를 이용해 풀었고, 기존 #1697에서 썼던 코드를 일부분 수정하여 풀 수 있었다.

하지만, #1697 에서처럼 큐에 집어넣을 때 방문지점을 표시하면 다른 두 번째 경우를 고려하지 않게 되므로 오답이 된다. 따라서, 큐에 push할 때가 아닌 pop할 때 방문지점을 표시하면 해결할 수 있다.

	if (n+1>=0 && n+1<MAX && !visited[n+1]) {
            Q.push(make_pair(n+1, cnt+1));
        }
        if (n-1>=0 && n-1<MAX && !visited[n-1]) {
            Q.push(make_pair(n-1, cnt+1));
        }
        if (n*2>=0 && n*2<MAX && !visited[n*2]) {
            Q.push(make_pair(n*2, cnt+1));
        }

따라서 다음과 같이, push할때는 그냥 push만 하고

	int n = Q.front().first;
        int cnt = Q.front().second;
        Q.pop();

        visited[n] = true;

        if (res1 && res1==cnt && n==K) {
            resCnt++;
        }   //재방문

        if (!res1 && n==K) {
            res1 = cnt;
            resCnt++;
        }   //첫방문

위와 같이 pop 할때 visited에 방문 처리를 해주어야 한다. 또한, 처음 방문하는 경우와 다시 방문하는 경우를 각각 나누어 처리했으며, 재방문하는 조건문을 첫방문하는 조건문보다 먼저 써주어야 한다. 그렇지 않으면, 첫방문할때 resCnt를 한번 ++ 하고, 그 다음 조건문을 만났을때에도 resCnt를 ++ 하게 된다. 즉, 첫방문때 방문횟수를 +2나 하게 된다는 의미이다. 

#include <iostream>
#include <queue>

#define MAX 100005

using namespace std;

int N,K;
queue<pair<int,int>> Q;
bool visited[MAX];
int res1, resCnt;

void F(int a,int c) {
    visited[a] = true;
    Q.push(make_pair(a,c));

    while (!Q.empty()) {
        int n = Q.front().first;
        int cnt = Q.front().second;
        Q.pop();

        visited[n] = true;

        if (res1 && res1==cnt && n==K) {
            resCnt++;
        }   //재방문

        if (!res1 && n==K) {
            res1 = cnt;
            resCnt++;
        }   //첫방문        

        if (n+1>=0 && n+1<MAX && !visited[n+1]) {
            Q.push(make_pair(n+1, cnt+1));
        }
        if (n-1>=0 && n-1<MAX && !visited[n-1]) {
            Q.push(make_pair(n-1, cnt+1));
        }
        if (n*2>=0 && n*2<MAX && !visited[n*2]) {
            Q.push(make_pair(n*2, cnt+1));
        }
    }
}

int main() {
    cin.tie();
    cout.tie();
    ios::sync_with_stdio(false);

    cin >> N >> K;

    F(N,0);

    cout << res1 << '\n' << resCnt << '\n';

    return 0;
}