[알고리즘 C++] 17071 숨바꼭질 5 , 플러드필(flood fill)알고리즘

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

17071번: 숨바꼭질 5

이 문제는 두가지 경우를 생각해야 했다.

 

1. 수빈이와 동생이 같은 점에서 만나는 경우

2. 수빈이가 동생보다 먼저 도착해서 -1, +1을 반복하며 동생을 기다리는 경우

 

1번은 그냥 BFS를 돌리며 만나면 break 하면 되기 때문에 간단하지만 2번을 떠올리는 것이 관건인 문제였다.

 

visited배열을 2차원으로 할당하고 짝수, 홀수인 각 경우에 어떤 지점을 방문했었는지 체크한다.

 

즉, 어떤 지점에 동생이 도착했을 때의 turn이 홀수이고 과거에 수빈이가 홀수일 때 도착했었다면

수빈이가 -1, +1을 반복할 수 있기 때문에 결국 만날 수 있게 되는 것이다.

 

 

그리고 turn을 구하기 위해서 플러드필(flood fill) 알고리즘을 사용했다

같은 turn이면 같은 색을 칠해준다는 느낌으로.

 

BFS를 사용했기 때문에

1. qSize를 구해 몇번 pop & push를 반복할지 정한다.

2. 해당 횟수만큼 반복문을 돌리며 pop & push 한다.

3. 마지막에 turn을 +1 해준다.

 

위 상황을 반복한다면, 

 

이 코드의 경우 한번 pop & push할 때마다 큐에는 +1, -1, *2해준 총 3개의 값이 들어가기 때문에

qSize는

1 -> 3 -> 9 순으로 할당 될 것이다.

 

#include <bits/stdc++.h>
using namespace std;
int N, K, prevN, ok = 0, visited[2][500004], turn, flag;

int main()
{
    cin >> N >> K;
    if (N == K)
    {
        cout << 0;
        return 0;
    }
    queue<int> q;
    q.push(N);
    visited[0][N] += 1;

    while (q.size())
    {
        K += turn;
        if (visited[turn % 2][K])
        {
            ok = 1;
            break;
        }
        int qSize = q.size();

        for (int i = 0; i < qSize; i++)
        {
            int here = q.front();

            if (K > 500000)
            {
                flag = 1;
                break;
            }
            if (here == K)
            {
                ok = 1;
                break;
            }
            q.pop();
            for (int next : {here + 1, here - 1, here * 2})
            {
                if (next < 0 || next > 500000)
                {
                    continue;
                }
                if (visited[(turn + 1) % 2][next])
                    continue;
                q.push(next);
                visited[(turn + 1) % 2][next] = visited[turn % 2][here] + 1;
            }
        }
        if (flag)
            break;
        if (ok)
            break;
        turn += 1;
    }
    if (ok)
        cout << turn;
    if (flag)
        cout << -1;
}