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

백준의 숨바꼭질3(13549) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 아주 쉬운 BFS/DFS 문제이다. 본인은 BFS로 풀어보았다. 문제에서 사용한 배열로서 Visit[] 1차원 배열을 사용하였는데

   단순히, true / false를 통해서 방문을 했다 안했다가 아닌, int형 배열로 선언해서 해당 점에 몇 초만에 갔는지

   횟수를 저장해주었다.

2) 풀이는 간단하다. 시작점을 Queue에 넣어주고, Visit[시작점] = 0으로 설정해준다.

   어떠한 움직임이 없어도 시작점에 있을 수 있기 때문에, Visit[시작점] = 0 이 된 것이다.

   이 후, 순간이동을 하는 경우, 한칸 뒤로가는경우, 한칸 앞으로 가는 경우에 따라 알맞게 초를 계속해서 저장해주면서

   진행하면 된다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 100000 + 1
#define INF 999999999
using namespace std;
 
int N, K;
int Visit[MAX];
 
void Input()
{
    cin >> N >> K;
    for (int i = 0; i < MAX; i++)
    {
        Visit[i] = INF;
    }
}
 
int BFS()
{
    queue<int> Q;
    Q.push(N);
    Visit[N] = 0;
 
    while (Q.empty() == 0)
    {
        int Pos = Q.front();
        Q.pop();
 
        if (Pos == K) return Visit[K];
        
        if (Pos + 1 < MAX && Visit[Pos + 1] > Visit[Pos] + 1)
        {
            Visit[Pos + 1] = Visit[Pos] + 1;
            Q.push(Pos + 1);
        }
 
        if (Pos - 1 >= 0 && Visit[Pos - 1] > Visit[Pos] + 1)
        {
            Visit[Pos - 1] = Visit[Pos] + 1;
            Q.push(Pos - 1);
        }
 
        if (Pos * 2 < MAX && Visit[Pos * 2] > Visit[Pos])
        {
            Visit[Pos * 2] = Visit[Pos];
            Q.push(Pos * 2);
        }
    }
}
 
void Solution() 
{
    int R = BFS();
    cout << R << endl;
}
 
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;
}