[ 백준 1697 ] 숨바꼭질 (C++)

백준의 숨바꼭질(1697) 문제입니다.

( www.acmicpc.net/problem/1697 )

[ 문제설명 ]

- 수빈이의 위치와, 동생의 초기 위치를 입력 받습니다.

- 수빈이는 +1 칸, -1칸 , x2 칸을 움직일 수 있고, 이 때 수빈이가 가장 빨리 동생을 찾을 수 있는 방법을 찾는 문제입니다.

[ 풀이방법 ]

1) 수빈이의 처음 위치에서 부터 BFS를 돌려주면 됩니다. (BFS를 돌리면, 가장 최단거리가 나오기 때문)

2) BFS를 돌리면서 Queue에 수빈이의 위치와, 시간을 같이 넣어서, 수빈이가 한번 움직일 때 마다 시간을++ 해주면 됩니다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 100000 + 1
 
using namespace std;
 
int N, K;
bool Visit[MAX];
 
int dx[] = { -1, 1 };
 
void Input()
{
    cin >> N >> K;
}
 
void BFS(int a)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, 0));
    Visit[a] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int t = Q.front().second;
        Q.pop();
 
        if (x == K)
        {
            cout << t << endl;
            return;
        }
 
        for (int i = 0; i < 2; i++)
        {
            int nx = x + dx[i];
            if (nx >= 0 && nx < MAX)
            {
                if (Visit[nx] == false)
                {
                    Q.push(make_pair(nx, t + 1));
                    Visit[nx] = true;
                }
 
            }
        }
        if (x * 2 < MAX)
        {
            if (Visit[x * 2] == false)
            {
                Q.push(make_pair(x * 2, t + 1));
                Visit[x * 2] = true;
            }
        }        
    }
}
 
void Solution()
{
    BFS(N);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}