[알고리즘 문제] 백준1679 - 숨바꼭질

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

1697번: 숨바꼭질

문제는 최단시간을 구해야 하는 문제이기 때문에 bfs로 풀어야 합니다. 백준 토마토 문제와 비슷한데, 하나씩 이동해가면서 수빈이가 동생의 위치에 도달하면 그때의 최소 경로수를 출력하면 됩니다.

 

전체적인 해결과정은,

현재 나의 지점(current)에서 3가지의 경우(+1, -1, x2)로 이동할 수 있으면 이동합니다(que에 넣어 줍니다.) 이때 한번 이동했기 때문에 time++을 출력합니다. 다음 정보를 que에서 빼오면서 빼온 위치가 도착지점과 같으면 몇번 이동했는지, time을 출력하면 됩니다.

 

여기서 visited[]를 사용한 이유는 한번 방문한 곳은 다른 경우의 수가 방문하지 않기 위함 입니다. 한번 방문한 곳에 또 방문했다는 것은 최소경로가 아니기 때문이며 처음 한번 방문한 경우만 최소경로이기 때문입니다.

 

#include <iostream>
#include <queue>

using namespace std;

int main()
{

    int me, you;
    cin >> me >> you;
    queue<int> que;
    que.push(me);

    int time = 0;
    bool visited[100001] = {0};
    bool isFind = false;
    while (1)
    {
        int size = que.size();

        for (int i = 0; i < size; i++)
        {
            me = que.front();
            que.pop();

            if (me == you)
            {
                isFind = true;
                break;
            }

            if (me > 0 && !visited[me - 1])
            {
                visited[me - 1] = true;
                que.push(me - 1);
            }
            if (me < 100000 && !visited[me + 1])
            {
                visited[me + 1] = true;
                que.push(me + 1);
            }

            if (me * 2 <= 100000 && !visited[me * 2])
            {
                visited[me * 2] = true;
                que.push(me * 2);
            }
        }
        if (isFind)
        {
            break;
        }
        time++;
    }
    cout << time;
    return 0;
}