재귀 (4) - 플러드 필 (Flood Fill)

1. 알고리즘 개요

Flood Fill은 말 그대로 색칠 알고리즘이다. 우리가 그림판을 이용할 때 물감통 모양의 아이콘을 클릭하고 어떠한 도형의 내부를 클릭하면 해당 도형의 내부만 색칠된다. 또 우리가 지뢰찾기 게임을 할 때 지뢰가 없는 영역을 누르면 근처의 지뢰가 없는 영역이 전부 눌러지게 된다. 이러한 알고리즘을 내부적으로 어떻게 구현할까?

 

[그림] 그림판 칠하기

 

우리는 이러한 기능을 구현하기 위해 재귀함수를 이용하여 좌표를 움직이며 색칠을 진행하는 알고리즘을 고안할 수 있다. 만약 현재 좌표가 선택한 곳(흰색)의 색상과 같은 경우, 그 곳을 원하는 색상(파란색)으로 변경하고, 현재 좌표가 선택한 곳(흰색)의 색깔과 다른 경우(검정색) 다른 방향으로 움직이는 등의 알고리즘을 생각해볼 수 있다. 아래는 FloodFill 알고리즘을 시각화 한 영상이다.

 

 

2. 소스 코드

재귀함수를 이용하면 이러한 알고리즘을 구현하는 것은 의외로 간단하다. 맨 처음 select의 값은 -1로 지정이 된다. select 값이 음수라는 것은 알고리즘의 시작을 알리며 최초 위치의 색상이 select의 값으로 지정된다. 여기에서는 0이 빈칸이기 때문에 만약 빈칸을 선택했다면 select의 값은 0이 된다. 만약 현재 위치가 이미지의 사이즈를 넘어가거나, select의 색상과 다른 경우(검정색인 경우) 현재 이미지를 리턴한다. 이미지를 리턴한다는 것은 이동방향을 다른 방향으로 전환한다는 의미이다. 

 

매 위치에서 이미지의 사이즈를 넘지 않거나 select와 색상이 같은 경우 그 곳은 빈칸이라는 의미이므로 원하는 색상으로 색칠하고현재 위치에 Seed를 두고 (영상의 붉은 색 이동하는 점) 좌, 우, 상, 하로 탐색을 시도한다. 네 방향을 탐색하다가 네 방향 모두에서 위의 조건(이미지 벗어나거나 다른 색상이거나)을 만나면 이전 Seed로 복귀한다.

 

#include <stdio.h>

#define SIZE 16

int image[SIZE][SIZE] = {
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0},
        {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
        {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
        {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
        {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
        {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
        {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
        {0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

int (*floodfill(int row, int col, int select, int color, int map[][SIZE]))[SIZE] {
    
    if (select < 0) {
        select = image[row][col];
    }

    if (row >= SIZE || col >= SIZE || row < 0 || col < 0 ||
        image[row][col] != select) {
        return map;
    }

    map[row][col] = color;
    floodfill(row + 1, col, select, color, map);
    floodfill(row - 1, col, select, color, map);
    floodfill(row, col + 1, select, color, map);
    floodfill(row, col - 1, select, color, map);
}

void print(int image[][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%d ", image[i][j]);
        }
        printf("\n");
    }
}

int main() {
    print(floodfill(7, 7, -1, 2, image));
    return 0;
}

 

실행 결과는 아래와 같다. (1, 1) 위치를 선택하면 도형 바깥쪽을 색칠하고, (7, 7) 위치를 선택하면 도형 내부를 색칠한다. 실행 결과를 보면 우리가 작성한 알고리즘이 잘 작동하는 것을 알 수 있다.

 

"""
floodfill(1, 1, -1, 2, image):

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2
2 2 2 2 1 0 1 1 1 1 1 1 1 2 2 2
2 2 2 1 0 0 0 0 0 0 0 0 1 2 2 2
2 2 1 0 0 0 0 0 0 0 0 0 0 1 2 2
2 2 1 0 0 0 0 0 0 0 0 0 0 1 2 2
2 2 1 0 0 0 0 0 0 0 0 0 0 1 2 2
2 2 1 0 0 0 0 0 0 0 0 0 0 1 2 2
2 2 1 0 0 0 0 0 0 0 0 0 0 1 2 2
2 2 1 0 1 1 1 0 0 0 0 0 0 1 2 2
2 2 2 1 2 2 2 1 1 1 0 0 0 1 2 2
2 2 2 2 2 2 2 2 2 2 1 1 1 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

floodfill(7, 7, -1, 2, image):

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 2 1 1 1 1 1 1 1 0 0 0
0 0 0 1 2 2 2 2 2 2 2 2 1 0 0 0
0 0 1 2 2 2 2 2 2 2 2 2 2 1 0 0
0 0 1 2 2 2 2 2 2 2 2 2 2 1 0 0
0 0 1 2 2 2 2 2 2 2 2 2 2 1 0 0
0 0 1 2 2 2 2 2 2 2 2 2 2 1 0 0
0 0 1 2 2 2 2 2 2 2 2 2 2 1 0 0
0 0 1 2 1 1 1 2 2 2 2 2 2 1 0 0
0 0 0 1 0 0 0 1 1 1 2 2 2 1 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
"""

 

모든 소스코드는 Github에서 확인할 수 있습니다.

gusdnd852/TIL

 

3. Reference