Flood Fill (BOJ 17071 숨바꼭질5)

Flood Fill이란?

다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘
주로 그림 프로그램에서 특정 영역에 "채우기" 도구에 사용
DFS(재귀함수) 혹은 BFS(Queue)를 활용해 구현
from. wiki

알고리즘

1. x 또는 y가 범위를 벗어나면 return
2. Map[y][x]의 색상이 현재 색상과 동일하지 않으면 return
3. 4방향(동서남북)를 순서대로 탐색 (재귀 혹은 BFS)

예시 문제

숨바꼭질5

풀이

1. 거리를 레벨(움직인 시간)의 홀수, 짝수로 구분
2. 매 레벨마다 동생과 수빈의 움직임을 업데이트 (turn)
3. 수빈의 경우 BFS로 탐색하되 각 레벨을 구분지어 탐색 (qsize)
4. 수빈과 동생이 같은 구간에 있고, 수빈이 해당 장소에 도착한 기록이 존재하는 경우 현재 레벨을 리턴

코드

#include<bits/stdc++.h>
#define prev aa
typedef long long ll;


using namespace std;

int N, K, ret = -1;
int turn = 0;
bool ok = false;


int DP[2][500004] = {0,};
vector<int> moveTo = {
    0, 1, -1
}; // {2, 0}, {1, 1}, {1,-1}로도 표현 가능 ({배수, 더하기})
stack<int> path;
vector<int> pathSample;

void input(){
    cin >> N >> K;
}

bool rangeCheck(int spot){
    return 0 <= spot && spot <= 500000; 
}

void floodFill(){
    int SB = N;
    int sis = K;

    if(SB == sis) {
        ok = true;
        return;
    }

    queue<int> quePath;

    quePath.push(SB);
    DP[0][SB] = 1;

    while(!quePath.empty()){
        
        sis += ++turn; // 다음 레벨의 탐색에 들어오면 turn++

        if(!rangeCheck(sis)) break;

        if(DP[turn%2][sis]){
            ok = true;
            ret = turn;
            break;
        }

        int qsize = quePath.size(); // 현재 레벨의 qsize를 저장
        for(int i=0; i< qsize; i++){ // 현재 레벨의 queue 내 모든 지점을 탐색
            int SB = quePath.front();
            quePath.pop();

            for(int i=0; i<moveTo.size(); i++){ // for(int next: {now+1, now-1, now*2})
                int next = SB + moveTo.at(i);
                if(next == SB) next *= 2;

                if(!rangeCheck(next)) continue;
                if(DP[turn%2][next]) continue;

                DP[turn%2][next] = DP[(turn+1)%2][SB]+1;

                if(next == sis){
                    ok = true;
                    break;
                }

                quePath.push(next);
            }
            if(ok) break;
        }

        if(ok) break;
    }
}

void output(){
    if(ok) cout << turn << endl;
    else   cout << -1 << endl;
}

void run(){
    input();
    floodFill();
    output();
}

int main(){
    run();
    return 0;
}

후기

수강 중인 알고리즘 강의에서 최초로 등장한 플래티넘 문제
직접 풀어보려 BFS로 시도하다 segment fault만 떠서 포기

얼른 답안을 참고하니 flood fill이라는 생소한 알고리즘을 활용하길래
살짝 당황했지만 오히려 빨리 보길 다행이었다는 생각

이런 문제는 해당 알고리즘을 모르는 경우라면
시간을 얼마나 줘도 잘 풀리지 않으니
차라리 후딱 보고 얼른 기록하는 편이 나은 듯 싶다.

아무튼 완탐, BFS, DFS만 반복하다가
오랜만에 본 새로운 알고리즘이라 반가운 마음에 기록

언젠간 쓸 일이 있겠지

참고자료

위키피디아
인프런 큰돌 10주 완성 C++ 코딩테스트
https://www.educative.io/answers/flood-fill-algorithm-in-cpp