[백준][C++] 12851: 숨바꼭질 2

문제

풀이

• BFS를 이용하여 해결한다. 
• 이전에 이동했던 위치인 visited를 큐에 넣을 때 true로 세팅하지 않고 꺼낼 때, 세팅하여 중복된 경로도 추가될 수 있도록 한다. 
• 이동할 수 있는 방법 별로 큐에 넣는다.

코드

#include <iostream>
#include <queue>
#include <map>
#include <climits>

using namespace std;

typedef struct
{
    int X;
    int dist;
}type;

queue<type> q;
bool visited[100002];
map<int, int> answer_map;

int main()
{
    int N, K;
    int answer = INT_MAX;

    cin >> N >> K;

    q.push({ N, 0 });
    visited[N] = true;

    while (!q.empty())
    {
        type current = q.front();
        q.pop();

        int current_X = current.X;
        int current_dist = current.dist;
        // 중복 경로 추가를 위해 pop한 다음에 visited를 true로 세팅
        visited[current_X] = true;

        if (current_dist > answer)
        {
            continue;
        }

        if (current_X == K)
        {
            answer = min(answer, current_dist);

            if (answer_map.find(current_dist) != answer_map.end())
            {
                answer_map[current_dist]++;
            }
            else
            {
                answer_map[current_dist] = 1;
            }
        }

        int next_X;

        // 이동할 수 있는 방법 별로 q에 push
        next_X = current_X * 2;
        if (next_X >= 0 && next_X <= 100001 && !visited[next_X])
        {
            q.push({ next_X, current_dist + 1 });
        }

        next_X = current_X + 1;
        if (next_X >= 0 && next_X <= 100001 && !visited[next_X])
        {
            q.push({ next_X, current_dist + 1 });
        }

        next_X = current_X - 1;
        if (next_X >= 0 && next_X <= 100001 && !visited[next_X])
        {
            q.push({ next_X, current_dist + 1 });
        }
    }

    cout << answer << endl;
    cout << answer_map[answer];

    return 0;
}