2차원 격자(grid)에 문자열 형태의 색상 "r", "g", "b"가 저장되어 있다고 가정해 보겠습니다. 이때 r행 c열 위치에서 목표 색상(target)으로 플러드 필(flood fill) 연산을 수행해야 합니다. 플러드 필 연산이란 grid[r][c]와 상·하·좌·우로 연결되어 있으면서 시작 지점과 같은 색상을 가진 모든 칸을 한꺼번에 목표 색상으로 바꾸는 작업을 말합니다.
예를 들어 입력이 다음과 같다면,
| R | R | R |
| R | G | B |
| G | B | B |
출력 결과는 아래와 같습니다.
| G | G | G |
| G | G | B |
| G | B | B |
grid[0][0]에 연결된 빨간색("r") 칸들이 모두 초록색("g")으로 변경되었기 때문입니다. 반면 대각선 방향이나 다른 색상으로 막혀 있는 칸들은 그대로 유지됩니다.
해결 접근 방법
이 문제는 DFS(깊이 우선 탐색)을 활용해 해결할 수 있습니다. 단계별 절차는 다음과 같습니다.
- 이미 방문한 좌표를 추적하기 위한 집합(set)
seen을 정의합니다. oldcolor := matrix[r][c]로 시작 지점의 기존 색상을 저장합니다.dfs(i, j)함수를 정의합니다.- i와 j가 행렬 범위 안에 있고, (i, j)를 아직 방문하지 않았으며, matrix[i][j]가 oldcolor와 같다면:
- seen에 (i, j)를 추가합니다.
- matrix[i][j] := target으로 색상을 변경합니다.
- dfs(i+1, j), dfs(i, j+1), dfs(i, j-1), dfs(i-1, j)를 순서대로 재귀 호출합니다.
- 메인 메서드에서는 dfs(r, c)를 호출한 뒤 matrix를 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제 코드
class Solution:
def solve(self, matrix, r, c, target):
def dfs(i, j):
if (
i >= 0
and i < len(matrix)
and j >= 0
and j < len(matrix[0])
and (i, j) not in seen
and matrix[i][j] == oldcolor
):
seen.add((i, j))
matrix[i][j] = target
dfs(i + 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
dfs(i - 1, j)
seen = set()
oldcolor = matrix[r][c]
dfs(r, c)
return matrix
ob = Solution()
matrix = [ ["r", "r", "r"], ["r", "g", "b"], ["g", "b", "b"] ]
r = 0
c = 0
target = "g"
print(ob.solve(matrix, r, c, target))입력
matrix = [ ["r", "r", "r"], ["r", "g", "b"], ["g", "b", "b"] ] r = 0 c = 0 target = "g"
출력
[ ['g', 'g', 'g'], ['g', 'g', 'b'], ['g', 'b', 'b']]
동작 원리 정리
이 알고리즘은 시작 좌표에서 출발해 조건을 만족하는 인접 칸으로 재귀적으로 확장하며 색상을 덮어씁니다. 각 칸은 최대 한 번만 방문되므로 시간 복잡도는 O(N×M)(N은 행 개수, M은 열 개수)이며, 공간 복잡도 역시 방문 집합과 재귀 호출 스택 때문에 O(N×M)입니다. 만약 매우 큰 격자에서 재귀 깊이 제한(RecursionError)이 걱정된다면, 스택 자료구조를 이용한 반복문(iterative) 방식으로 DFS를 구현하는 것도 좋은 대안입니다.