[ 백준 ] 12851 / 숨바꼭질 2

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
186/228
post-thumbnail

# Appreciation

/*
 * Problem :: 12851 / 숨바꼭질 2
 *
 * Kind :: BFS
 *
 * Insight
 * - 동생을 찾을 수 있는 가장 빠른 시간과 더불어
 *   찾을 수 있는 방법의 수를 구해야 한다
 *   + 동생을 찾으면 끝이 아니다...
 *     # 동생을 찾은 위치를 방문한 적이 있더라도
 *       또 방문할 수 있어야 한다!
 *       -> 어떻게?
 *
 * - BFS 에서 Queue 에 넣어줄 때
 *   방문처리를 하면 안된다!
 *   + 예를 들어, 현재 Queue 에 5, 11 이 있다고 하면,
 *     5 => 10, 11 => 10 이렇게 갈 수 있는데
 *     만약 5 => 10 에서 10 에 방문처리를 해버리면
 *     11 => 10 일 때, 10 이 방문처리되었다고 생각해서 이를 불가능하다고 판단한다
 *     # 하지만 10 에 동생이 있었다면?
 *       그러니, Queue 에 넣을 때 방문처리를 하는 것이 아닌
 *       뺄 때 방문처리를 해야한다!
 *       -> 즉, push 할 때가 아닌 pop 할 때 방문처리를 하자
 *
 * Point
 * - 수빈이가 동생을 찾을 때
 *   N >= K 이면
 *   수빈이는 X-1 의 방법으로만 움직여서 동생을 찾아야 한다
 *   + 따라서, 이 때는 굳이 BFS 를 돌리지 않고도
 *     N-K 가 동생을 찾는 가장 빠른 시간이고
 *     방법의 수는 1 가지이다.
 *
 * - N < K 인 경우,
 *   (2*K-1) 의 위치까지만 탐색하면 된다
 *   + 현재위치가 C 라면
 *     C < K 일 때, X+1, 2*X 의 방법으로 이동하고
 *     C > K 일 때, X-1 의 방법으로 이동한다
 *     # 2*K 이상의 위치로 가면 K 이상을 되돌아와야 한다
 *       -> N 에서 X+1 의 방법으로만 이동해도 N-K 가 걸리는데
 *          N >= 0 이므로 2*K 이상의 위치로 가는 것은 비효율적이다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, K;
    cin >> N >> K;

    // Control : Output
    if (N >= K) { /* 수평선 기준, 동생의 위치가 수빈이의 위치보다 왼쪽에 있을 때 */
        /* X-1 의 방법으로만 이동해서 찾아야함 */
        cout << N-K << endl;
        cout << 1 << endl;
        exit(0);
    }

    // Process
    bool isVisited[2*K]; /* (2*K-1) 의 위치까지만 탐색 */
    memset(isVisited, false, sizeof(isVisited)); /* 초기화 */

    queue<int> que; /* BFS Queue */
    que.push(N); /* push 할 때 방문처리 하지 않음 */

    int minTime = -1, numMethods = 0; /* 동생을 찾는 가장 빠른 시간, 그 방법의 수 */
    int time = -1; /* 현재 시간 */
    while (not(que.empty())) {
        time++;
        int size = que.size();
        while (size--) { /* 이 while 문 안에서 pop 된 현재 위치들은 time 이 같음 */
            int cp = que.front(); que.pop(); /* 현재 위치 */

            isVisited[cp] = true; /* pop 할 때 방문처리 */

            if (cp == K) { /* 동생을 찾았으면 */
                if (minTime == -1) { /* 현재 시간이 동생을 찾는 가장 빠른 시간 */
                    minTime = time; /* 기록 */
                } numMethods++; /* 방법의 수 증가 */
                continue; /* 찾았으면 더이상 움직임이 필요치 않으므로 넘어감 */
            }

            /* X-1, X+1, 2*X 로 움직임 */
            int D[3] = {-1, +1, cp};
            for (int dp : D) {
                int np = cp + dp;
                if (np >= 0 && np < 2*K && not(isVisited[np])) {
                    /* que 에 push 할 때 방문처리 하지 않음
                     * 따라서 다음위치 np 가 동생의 위치여도 여러번 방문 가능 */
                    que.push(np);
                }
            }
        }
        /* 동생을 찾았으면 BFS 종료 */
        if (minTime != -1) break;
    }

    // Control : Output
    cout << minTime << endl;
    cout << numMethods << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글