Typiler

플러드 필 알고리즘은 다차원 배열의 어떤 카과 연결된 영역을 찾는 알고리즘 입니다. 그림 프로그램에서 연결된 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며, 바둑이나 지뢰 찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지를 결정할 때에도 사용됩니다.

동작과정

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 한다.
2. 큐에 원소를 꺼내어 그 칸에 인접한 칸(ex. 상,하,좌,우)에 대하여 3과 같이 동작한다.
3. 인접한 칸에 대하여 방문여부를 판단하여 처음 방문했다면 방문 표시를 남기고 큐에 넣는다.
4. 큐의 모든 원소가 빌 때까지 2의 행동을 반복한다.

시간복잡도

모든 칸이 큐에 1번 들어가는 것이 보장되므로 칸이 N개일 때 시간복잡도는 O(N) 입니다.

참고사이트

https://choijiuen.tistory.com/99

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

기본코드

2차원 배열 (4*4) 에서 2,1 에서 시작하여 모든 배열을 도는데 걸리는 cnt를 알아내는 예제입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

class PNode {
    int y, x;
    PNode(int a, int b)
    {
        y = a;
        x = b;
    }
}

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int [][]map = new int[4][4];
    static Queue<PNode> q = new LinkedList<PNode>();

    public static void main(String[] args) throws IOException {        

        map[2][1] = 1;
        q.add(new PNode(2, 1));

        int[][] direct = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int cnt = 0;

        while(!q.isEmpty()) {
            PNode now = q.poll();

            //now에서 다음 퍼지는 길 모두 등록
            for (int t = 0; t<4; t++ ) {
                int ny = now.y + direct[t][0];
                int nx = now.x + direct[t][1];
                if (ny < 0 || nx < 0 || ny >= 4 || nx >= 4) continue;
                if (map[ny][nx] != 0) continue;

                map[ny][nx] = map[now.y][now.x]+ 1;
                if (map[ny][nx] > cnt) cnt = map[ny][nx];

                q.add(new PNode(ny, nx));
            }
        }

        bw.write(cnt + "\n");

        br.close();
        bw.close();
    }
}

실행하여 map 의 변화를 알아보면 처음 map은 (2,1) 에서 시작하기 때문에 아래와 같다.

[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 1, 0, 0]
[0, 0, 0, 0]

전부 완료되었을때 map 은 아래와 같이 변경된다.

[4, 3, 4, 5]
[3, 2, 3, 4]
[2, 1, 2, 3]
[3, 2, 3, 4]

위와 같은 결과로 모든 배열이 채워지는데 마지막 숫자인 5가 결과로 나타난다.