이 문제에서는 2차원 화면을 나타내는 2D 배열과, 색을 채워야 할 화면상 픽셀의 좌표, 그리고 새로 적용할 색상이 주어집니다. 우리의 과제는 현재 픽셀과 그 픽셀과 같은 색으로 연결된 모든 인접 픽셀을 새로운 색으로 칠하는 프로그램을 작성하는 것입니다.
그림판 프로그램에서 색 채우기 기능은 원하는 색을 선택한 뒤 브러시(채우기 도구)로 특정 픽셀을 클릭하면 동작합니다. 클릭된 영역과 연결된 같은 색의 영역 전체가 한 번에 새로운 색으로 바뀌는 것이죠.
문제 예시
예제를 통해 문제를 더 자세히 이해해 보겠습니다.
입력: Screen[][] =
{{W, W, B, W, W, W, W, W},
{W, W, W, W, W, W, B, B},
{W, B, B, W, W, B, W, W},
{W, Y, Y, Y, Y, B, W, B},
{B, W, W, Y, Y, B, W, B},
{B, W, W, Y, Y, Y, Y, B},
{W, B, W, W, W, Y, W, W},
{W, W, B, B, W, Y, Y, W}};
X = 5, Y = 5, newColor = R
출력:
{{W, W, B, W, W, W, W, W},
{W, W, W, W, W, W, B, B},
{W, B, B, W, W, B, W, W},
{W, R, R, R, R, B, W, B},
{B, W, W, R, R, B, W, B},
{B, W, W, R, R, R, R, B},
{W, B, W, W, W, R, W, W},
{W, W, B, B, W, R, R, W}};(5, 5) 위치의 픽셀은 노란색(Y)이며, 이 픽셀과 상하좌우로 연결된 모든 노란색 픽셀이 빨간색(R)으로 변경된 것을 확인할 수 있습니다.
플러드 필 알고리즘이란?
플러드 필(Flood Fill) 알고리즘은 선택된 이전 색상과 동일한 색을 가진 픽셀만 새로운 색으로 채우는 방식입니다. 만약 해당 픽셀의 색이 대상 색상과 다르다면 그 픽셀은 채워지지 않습니다. 하나의 픽셀을 채운 후에는 해당 픽셀의 위, 아래, 왼쪽, 오른쪽 픽셀을 검사하여 같은 작업을 반복합니다.
해결 접근 방법
이 문제는 재귀(Recursion)를 활용해 해결할 수 있습니다. 먼저 색을 칠해야 할 첫 번째 픽셀을 찾은 다음, 그 픽셀의 4방향 이웃 픽셀들을 검사합니다. 이웃 픽셀이 시작 픽셀과 같은 색이라면 새로운 색으로 교체하고, 현재 픽셀의 이웃들에 대해 재귀적으로 같은 과정을 반복합니다. 만약 이웃 픽셀이 다른 색이라면 그대로 두고 넘어갑니다.
이 과정을 시작 픽셀과 같은 색을 가진 모든 인접 픽셀이 칠해질 때까지 반복한 뒤, 알고리즘을 종료하면 됩니다.
알고리즘 단계 정리
- 시작 좌표가 화면 범위를 벗어나면 종료합니다.
- 현재 픽셀의 색이 이전 색(oldColor)과 다르면 종료합니다.
- 현재 픽셀이 이미 새로운 색으로 칠해져 있으면 종료합니다(무한 재귀 방지).
- 현재 픽셀을 새로운 색으로 칠합니다.
- 상, 하, 좌, 우 네 방향에 대해 재귀 호출을 수행합니다.
C++ 구현 예제
아래는 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.
#include<iostream>
using namespace std;
#define M 8
#define N 8
void fillColorAdj(char screen[][N], int x, int y, char oldColor, char color){
if (x < 0 || x >= M || y < 0 || y >= N)
return;
if (screen[x][y] != oldColor)
return;
if (screen[x][y] == color)
return;
screen[x][y] = color;
fillColorAdj(screen, x+1, y, oldColor, color);
fillColorAdj(screen, x-1, y, oldColor, color);
fillColorAdj(screen, x, y+1, oldColor, color);
fillColorAdj(screen, x, y-1, oldColor, color);
}
void fillColor(char screen[][N], int x, int y, char color){
char oldColor = screen[x][y];
if(oldColor==color) return;
fillColorAdj(screen, x, y, oldColor, color);
}
int main(){
char screen[M][N] = {{'W', 'W', 'B', 'W', 'W', 'W', 'W', 'W'},
{'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B'},
{'W', 'B', 'B', 'W', 'W', 'B', 'W', 'W'},
{'W', 'Y', 'Y', 'Y', 'Y', 'B', 'W', 'B'},
{'B', 'W', 'W', 'Y', 'Y', 'B', 'W', 'B'},
{'B', 'W', 'W', 'Y', 'Y', 'Y', 'Y', 'B'},
{'W', 'B', 'W', 'W', 'W', 'Y', 'W', 'W'},
{'W', 'W', 'B', 'B', 'W', 'Y', 'Y', 'W'}};
int x = 5, y = 5;
char color = 'R';
cout<<"The initial screen cordinates are : \n";
for (int i=0; i<M; i++){
for (int j=0; j<N; j++)
cout<<screen[i][j]<<"\t";
cout<<endl;
}
fillColor(screen, x, y, color);
cout<<"\nThe screen cordinates after coloring are : \n";
for (int i=0; i<M; i++){
for (int j=0; j<N; j++)
cout<<screen[i][j]<<"\t";
cout<<endl;
}
}실행 결과
The initial screen cordinates are : W W B W W W W W W W W W W W B B W B B W W B W W W Y Y Y Y B W B B W W Y Y B W B B W W Y Y Y Y B W B W W W Y W W W W B B W Y Y W The screen cordinates after coloring are : W W B W W W W W W W W W W W B B W B B W W B W W W R R R R B W B B W W R R B W B B W W R R R R B W B W W W R W W W W B B W R R W
마무리
플러드 필 알고리즘은 그림판의 색 채우기 기능뿐만 아니라 미로 찾기, 이미지 처리, 영역 분할 등 다양한 분야에서 활용되는 핵심 알고리즘입니다. 재귀를 이용한 구현은 코드가 직관적이라는 장점이 있지만, 화면 크기가 매우 클 경우 스택 오버플로우가 발생할 수 있으므로 이 경우 BFS(너비 우선 탐색)나 명시적인 스택을 사용한 반복문 방식으로 대체하는 것이 좋습니다.