--- title: "채우기는 어디서 멈출지를 색으로 정한다" description: "매치3의 같은 색 묶기, 페인트 통, 지뢰찾기의 빈 칸 열기가 전부 플러드 필(flood fill) 하나입니다. 이웃을 색으로 정하는 탐색이 어디서 터지고, 네 방향과 여덟 방향이 무엇을 바꾸는지 봅니다." author: "유니얼" pubDate: 2026-09-15 updatedDate: 2026-09-18 category: "programming/algorithm/graph" tags: ["탐색", "격자"] canonical: https://blog.unialgames.com/posts/algo-flood-fill/ --- 세 가지 기능이 있습니다. - 매치3에서 같은 색 블록이 몇 개나 붙어 있는지 센다 - 그림 도구에서 페인트 통으로 한 영역을 칠한다 - 지뢰찾기에서 빈 칸을 누르면 주변 빈 칸이 한꺼번에 열린다 셋 다 **한 칸에서 출발해 조건에 맞는 이웃으로 계속 번져 나가는 일**입니다. 코드로는 거의 같고, 이 알고리즘의 이름이 **플러드 필(flood fill)** 입니다. 격자를 훑는 탐색과 다른 점은 하나뿐입니다. **어디까지 갈 수 있는지를 지형이 아니라 칸의 값이 정합니다.** ## 이웃을 색이 정한다 지금까지 격자에서 이웃을 고르는 조건은 둘이었습니다. 맵 안이어야 하고, 벽이 아니어야 합니다. 채우기에는 조건이 하나 더 붙습니다. ```csharp void Fill(int sx, int sy) { int target = grid[sx, sy]; // 시작 칸의 값이 기준이 된다 var stack = new Stack<(int, int)>(); stack.Push((sx, sy)); filled[sx, sy] = true; while (stack.Count > 0) { var (x, y) = stack.Pop(); Paint(x, y); for (int d = 0; d < DX.Length; d++) { int nx = x + DX[d]; int ny = y + DY[d]; if (nx < 0 || ny < 0 || nx >= Width || ny >= Height) continue; if (filled[nx, ny]) continue; if (grid[nx, ny] != target) continue; // 이 줄이 경계다 filled[nx, ny] = true; stack.Push((nx, ny)); } } } ``` `grid[nx, ny] != target` 한 줄이 이 알고리즘의 전부입니다. 벽처럼 지도에 박혀 있는 경계가 아니라 **시작 칸이 무엇이었느냐에 따라 매번 새로 생기는 경계**입니다. 같은 지도라도 파란 블록에서 시작하면 파란 영역이, 빨간 블록에서 시작하면 빨간 영역이 잡힙니다. ## 스택이든 큐든 결과는 같다 담아 두는 자리를 스택으로 두면 한 갈래로 길게 뻗어 나가고, 큐로 두면 시작 칸에서 동심원처럼 퍼집니다. **그런데 칠해지는 칸의 집합은 똑같습니다.** 영역 전체를 칠하는 것이 목적이라 순서가 결과를 안 바꿉니다. 그래서 고르는 기준이 결과가 아니라 다른 데 있습니다. | 이럴 때 | 무엇으로 | | --- | --- | | 그냥 칠하기만 한다 | 아무거나. 스택이 코드가 짧습니다 | | 퍼지는 모습을 연출로 보여준다 | 큐. 시작점에서 물결처럼 번지는 그림이 나옵니다 | | 시작 칸에서 몇 칸 떨어졌는지가 필요하다 | 큐. 거리를 같이 기록할 수 있습니다 | 지뢰찾기에서 칸이 촤르륵 열리는 연출이나, 물이 번지는 효과에 한 칸씩 지연을 주고 싶다면 큐 쪽입니다. ## 재귀로 짜면 큰 영역에서 터진다 채우기를 재귀로 쓰면 코드가 아주 짧아집니다. ```csharp void Fill(int x, int y, int target) { if (밖이거나 이미 칠했거나 색이 다르면) return; filled[x, y] = true; Paint(x, y); Fill(x + 1, y, target); Fill(x - 1, y, target); Fill(x, y + 1, target); Fill(x, y - 1, target); } ``` **영역이 커지면 그대로 호출 깊이가 됩니다.** 512 곱하기 512 짜리 캔버스를 전부 칠하면 최악에 26만 번 중첩입니다. 스택 프레임 하나가 수십 바이트만 잡아도 남아나지 않습니다. 게임에서 스택 오버플로는 대개 프로세스 종료이고, `try` 로 잡히지도 않습니다. 칠할 영역의 크기를 내가 정하는 경우, 예를 들어 매치3 보드가 8 곱하기 8 이라면 재귀로 써도 됩니다. 캔버스나 큰 맵처럼 **크기를 사용자가 정하는 경우에는 반드시 직접 만든 스택이나 큐**로 씁니다. ## 네 방향이냐 여덟 방향이냐 이웃의 정의를 바꾸면 같은 지도에서 다른 영역이 나옵니다.
점선은 같은 색인데 안 칠해진 칸, 회색은 다른 색 칸 시작 네 방향 · 칠해진 칸 4개
대각선으로만 닿은 칸은 남의 영역이다.
점선은 같은 색인데 안 칠해진 칸, 회색은 다른 색 칸 시작 여덟 방향 · 칠해진 칸 11개
대각선을 이웃으로 치면 모서리 하나로 두 덩어리가 이어진다.
 같은 지도, 같은 시작 칸인데 네 칸이 칠해지기도 하고 열한 칸이 칠해지기도 합니다. **둘 중 무엇이 맞는지는 알고리즘이 아니라 게임 규칙이 정합니다.** - **매치3은 네 방향입니다.** 가로나 세로로 이어진 것만 매치로 치기 때문입니다. 여덟 방향으로 세면 모서리만 닿은 블록까지 한 덩어리가 됩니다 - **지뢰찾기는 여덟 방향입니다.** 칸에 적힌 숫자가 여덟 방향의 지뢰 수라서, 여는 규칙도 같은 여덟 방향이어야 앞뒤가 맞습니다 - **맵에서 섬을 셀 때는** 모서리로 닿은 땅을 한 섬으로 볼지부터 정합니다. 그 답이 방향 수입니다 여덟 방향에는 함정이 하나 더 있습니다. 벽이 대각선으로 맞물린 자리를 **모서리로 빠져나갑니다.** 막아야 한다면 양옆 두 칸이 모두 막혀 있을 때 그 대각선을 이웃에서 빼면 됩니다. ## 줄 단위로 채우면 큐가 작아진다 칸마다 큐에 넣는 방식은 넓은 영역에서 큐가 크게 부풀어 오릅니다. 페인트 통처럼 수만 칸을 칠하는 경우라면 **줄 단위로 처리하는 편**이 낫습니다. 스캔라인 플러드 필(scanline flood fill)이라고 부릅니다. 절차는 이렇습니다. 1. 꺼낸 칸에서 **왼쪽과 오른쪽으로 끝까지** 훑어 그 줄의 구간을 통째로 칠합니다 2. 칠한 구간의 **바로 위 줄과 아래 줄만** 살펴봅니다 3. 그 줄에서 아직 안 칠해졌고 색이 같은 구간을 찾아, 각 구간의 칸 하나씩만 큐에 넣습니다 큐에 들어가는 것이 칸 수가 아니라 **구간 수**가 됩니다. 가로로 긴 영역일수록 차이가 커집니다. 가로 1,000칸짜리 줄이 스무 개면 칸 단위로는 2만 개가 큐를 거쳐 가지만, 줄 단위로는 스무 번 남짓입니다. 대신 코드가 길어지고 구간 경계에서 실수하기 쉽습니다. 보드가 작은 게임에서는 굳이 쓸 이유가 없습니다. 큰 캔버스를 칠하는 도구를 만들 때 꺼내는 방법입니다. ## 색을 무엇으로 비교하나 칸에 든 것이 타일 번호나 블록 종류면 그냥 같은지 보면 됩니다. 픽셀 색이면 이야기가 달라집니다. 그림의 경계는 안티에일리어싱 때문에 **중간 색이 한두 픽셀 깔려 있습니다.** 정확히 같은 색만 이웃으로 치면 칠하고 난 뒤 원래 색의 테두리가 남습니다. 그래서 허용 오차를 둡니다. ```csharp bool SameColor(Color32 a, Color32 b, int tolerance) { return Mathf.Abs(a.r - b.r) <= tolerance && Mathf.Abs(a.g - b.g) <= tolerance && Mathf.Abs(a.b - b.b) <= tolerance; } ``` 채널별 차이를 보는 방식입니다. 세 채널의 거리를 재는 방법도 있는데, 어느 쪽이든 **오차를 키우면 반대 문제가 생깁니다.** 경계의 중간 색까지 같은 색으로 쳐 버리면 그 너머로 새어 나갑니다. 오차는 게임 화면을 보면서 맞추는 값이지 계산으로 나오는 값이 아닙니다. 알파를 빼먹는 것도 흔한 실수입니다. 투명한 영역은 RGB 가 제각각이라 눈에는 다 같아 보여도 값이 다릅니다. ## 다 칠하고 나면 채우기의 결과물은 보통 색이 아니라 **칸의 목록**입니다. 그 목록으로 무엇을 하느냐가 기능을 가릅니다. | 무엇을 만드나 | 어떻게 | | --- | --- | | 매치 판정 | 칸 수가 기준 이상이면 제거하고 점수를 준다 | | 선택 윤곽선 | 칠해진 칸 중 **이웃에 안 칠해진 칸이 있는** 것만 모으면 테두리가 된다 | | 영역 정보 | 칸 목록에서 가운데와 가장자리를 계산해 팝업이나 이펙트를 띄운다 | 지뢰찾기의 빈 칸 열기가 특히 재미있습니다. 규칙이 이렇습니다. - 주변 지뢰가 0인 칸은 열고, **이웃을 계속 퍼뜨립니다** - 숫자가 적힌 칸은 열되, **거기서 멈춥니다** 여는 것과 퍼뜨리는 것을 갈라 놓은 것입니다. 그래서 빈 영역이 통째로 열리고 그 가장자리에 숫자 한 겹이 함께 드러납니다. **경계 칸을 결과에 포함하되 프런티어에는 넣지 않는 것**, 이 손질이 채우기 계열에서 자주 쓰입니다. ## 정리 채우기는 이웃의 조건에 "값이 같아야 한다" 한 줄을 더한 탐색입니다. 경계가 지도에 박혀 있지 않고 시작 칸이 무엇이었느냐에 따라 매번 새로 생깁니다. 정할 것은 셋입니다. - **방향 수.** 네 방향과 여덟 방향은 같은 지도에서 다른 답을 냅니다. 게임 규칙이 정합니다 - **담아 두는 자리.** 결과는 같으니 연출이나 거리 계산이 필요한지로 고릅니다. 다만 영역 크기를 사용자가 정하는 경우 재귀는 쓰지 않습니다 - **같다는 것의 기준.** 타일 번호면 그냥 비교하고, 픽셀 색이면 허용 오차를 두되 너무 키우면 경계를 넘어 샙니다 비용은 칠한 칸 수에 비례합니다. 맵 전체가 아니라 **그 영역만** 훑기 때문에, 보드가 커져도 한 덩어리가 작으면 부담이 없습니다.