[Algorithm] 플러드필 알고리즘

FloodFill Algorithm?

• FloodFill은 SeedFill이라고도 불린다.

• 배열에서, 어떤 칸과 연결된 영역을 찾는 알고리즘이다.

• 지뢰찾기를 생각하면 떠올리기 쉽다.
  

• 위 그림에서 같은 인덱스 번호를 가진 칸은 같은 색으로 칠해졌고 이를 탐색할 수 있는 알고리즘이 플러드 필 알고리즘이다.

• 스택, DFS, BFS로 풀 수 있지만, 자신만의 방법으로 하나 선택하여 익혀두는 것이 좋을듯 하다.

  BFS로 FloodFill을 구현한 것을 서술하고자 한다

BFS로 구현한 FloodFill

• idx란, 구역화를 나누기 위한 것이다.

• 칸에서 같은 값을 가지고 있다면 같은 인덱스 값을 부여받는다.

• dr은 열을, dc란 행을 나타낸다 - 각 상, 하, 좌, 우
  

백준

• 백준에서 2가지 문제를 FloodFill을 사용하여 해결하였다.

• 코드에 주석을 달아 설명하고자 한다.

1) 백준 2146 - 다리만들기 (골드 3)

다리만들기 - 링크를 클릭하시면 이동합니다.

import java.util.*;
import java.io.*;

public class Main_16946 {

    private static int map[][], group[][], groupSize[], N, M;
    private static boolean visited[][];
    private static int dr[] = new int[]{-1, 1, 0, 0}; // 상하좌우
    private static int dc[] = new int[]{0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        N = Integer.parseInt(stk.nextToken()); // 행
        M = Integer.parseInt(stk.nextToken()); // 열
        map = new int[N][M];
        group = new int[N][M];

        for(int i = 0; i < N; i++) {
            String input = br.readLine();
            for(int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }
        // ===================== input end ============================

        // Group 찾기
        int idx = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
               if(map[i][j] == 0 && group[i][j] == 0)
                   floodFill(i, j, ++idx);
            }
        }

        // Group의 idx 별 칸 수 count
        groupSize= new int[idx+1];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                int groupIdx = group[i][j];
                groupSize[groupIdx]++;
            }
        }

        // 출력
        StringBuilder output = new StringBuilder();
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                output.append(countBlock(i, j));
            }
            output.append("\n");
        }
        System.out.println(output.toString());
    }

    // 벽이 있는 칸의 인접한 칸들의 그룹번호를 더하여 이동할 수 있는 칸의 개수 구하기
    private static int countBlock(int r, int c) {
        if(map[r][c] == 0) return 0;

        // 동일한 인덱스는 더하지 않기 위해 Set 이용
        Set<Integer> set = new HashSet<>();
        for(int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if(isOverRange(nr, nc) || group[nr][nc] == 0) continue;
            set.add(group[nr][nc]);
        }

        int cnt = 1;
        for(int idx : set) {
            cnt += groupSize[idx];
        }
        return cnt % 10;
    }


    // 플러드필 알고리즘: 주위 빈 칸(0) 모두 찾아 그룹화하기
    private static void floodFill(int r, int c, int idx) {

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r, c});
        group[r][c] = idx;

        while(!queue.isEmpty()) {
            int[] point = queue.poll();
            for(int d = 0; d < 4; d++) { // 4방 탐색하면서 그룹화 하기
                int nr = point[0] + dr[d];
                int nc = point[1] + dc[d];
                if(isOverRange(nr, nc) || group[nr][nc] != 0 || map[nr][nc] == 1) // 연결되어있는 지점
                    continue;
                queue.add(new int[]{nr, nc});
                group[nr][nc] = idx;
            }
        }
    }

    // 범위 체크
    private static boolean isOverRange(int r, int c) {
        if(r < 0 || c < 0 || r >= N || c >= M) return true;
        else return false;
    }
} 

2) 백준 16946 - 벽부수고 이동하기 4 (골드 2)

벽 부수고 이동하기 4 - 링크를 클릭하시면 이동합니다.

import java.io.*;
import java.util.*;

public class Main_2146 {
    static int N, map[][], indexedMap[][], minLength = Integer.MAX_VALUE;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static List<Point> lands;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력받기
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        indexedMap = new int[N][N];
        lands = new LinkedList<Point>();

        for(int i = 0; i < N; i++) {
            StringTokenizer stk = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }
        // ================== input end ========================

        // 한 면 이상 바다와 붙어있는 지점 리스트에 넣기 - 육지 찾기
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(map[i][j] == 0) continue; // 바다이면 살펴볼 필요가 없다.

                for(int d = 0; d < 4; d++) {
                    int nr = i + dr[d];
                    int nc = j + dc[d];

                    if(isOverRange(nr, nc)) continue;

                    // 한 면이라도 바다와 붙어있는지 확인해서 붙어있다면 lands에 넣기 - 끝
                    if(map[nr][nc] == 0) {
                        lands.add(new Point(i, j));
                        break;
                    }
                }
            }
        }

        // 리스트에서 인덱스 별 지도 만들기, 한 면이 바다와 맞닿아이지 않은 육지는 -1로 표시 / 바다는 0으로 표시
        int idx = 1; // 육지 인덱스 부여
        for(Point p : lands) {
            if(indexedMap[p.r][p.c] >= 1) continue; // 이미 육지라고 인덱스화 되었으므로 pass
            else floodFill(p.r, p.c, idx++);
        }

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(indexedMap[i][j] >= 1) continue;
                indexedMap[i][j] = 0;
            }
        }
        // ================= 인덱스화 잘 되었는지 확인 완료 ================

        // 육지에서 다른 육지로의 최소 거리 구하기
        for(Point p : lands) {
            search(p.r, p.c);
        }

        System.out.println(minLength);
    }

    // 최소 거리 찾기
    private static void search(int r, int c) {
        Queue<Point> queue = new LinkedList<Point>();
        boolean[][] visited = new boolean[N][N];
        visited[r][c] = true;
        queue.add(new Point(r, c, 0));

        while(!queue.isEmpty()) {
            Point p = queue.poll();

            for(int d = 0; d < 4; d++) {
                int nr = p.r + dr[d];
                int nc = p.c + dc[d];

                if(isOverRange(nr, nc) || visited[nr][nc]) continue;

                if(indexedMap[nr][nc] >= 1 && indexedMap[nr][nc] != indexedMap[r][c]) {
                    minLength = Math.min(p.d, minLength);
                    return;
                }

                if(indexedMap[nr][nc] == 0) {
                    visited[nr][nc] = true;
                    queue.add(new Point(nr, nc, p.d + 1));
                }
            }
        }
    }

    // 같은 육지별로 인덱스화
    private static void floodFill(int r, int c, int idx) {
        Queue<Point> queue = new LinkedList<>();
        boolean visited[][] = new boolean[N][N];

        queue.add(new Point(r, c));
        indexedMap[r][c] = idx;

        while(!queue.isEmpty()) {
            Point p = queue.poll();

            for(int d = 0; d < 4; d++) {
                int nr = p.r + dr[d];
                int nc = p.c + dc[d];

                if(isOverRange(nr, nc)) continue;
                if(visited[nr][nc] || map[nr][nc] == 0) continue;

                visited[nr][nc] = true;
                indexedMap[nr][nc] = idx;
                queue.add(new Point(nr, nc));
            }
        }
    }

    private static boolean isOverRange(int r, int c) {
        if(r < 0 || c < 0 || r >= N || c >= N) return true;
        else return false;
    }

    private static class Point {
        int r;
        int c;
        int d; // distance : 지나온 칸의 수

        Point(int r, int c) {
            this.r = r;
            this.c = c;
        }

        Point(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }
    }
}