Flood Fill
이미지는 각 숫자가 한 픽셀의 색상을 나타내는 정수 그리드입니다. 이미지가 행 목록으로 주어지고, 시작 픽셀의 행은 sr, 열은 sc이며, 새 color가 주어집니다. 시작 픽셀이 속한 영역을 다시 칠하세요. 즉, 시작 픽셀과 같은 색을 가진 픽셀 중 같은 색의 픽셀을 통해 위, 아래, 왼쪽 또는 오른쪽으로 이동하여 도달할 수 있는 모든 픽셀을 다시 칠합니다. 다시 칠한 후의 이미지를 반환하세요.
함수
- imageinteger-2d-array
- 이미지를 픽셀당 하나의 숫자로 이루어진 행 목록으로
- srinteger
- 시작 픽셀의 행(0부터 셈)
- scinteger
- 0부터 세는 시작 픽셀의 열
- colorinteger
- 영역의 새로운 색상
- 반환값integer-2d-array
- 영역이 다시 그려진 후의 이미지
제약 조건
1 ≤ image.length ≤ 801 ≤ image[i].length ≤ 80- 모든 행의 길이가 같습니다.
0 ≤ image[i][j], color ≤ 655350 ≤ sr < image.length그리고0 ≤ sc < image[0].length
예제
- 입력
- image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
- 출력
- [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
- 설명
- 시작 지점에는 색상 1이 있습니다. 그 오른쪽의 1, 왼쪽 열 아래로 이어지는 1들과 맨 아래 행의 1들, 그리고 오른쪽 아래 모서리 바로 위의 1은 모두 시작 지점과 연결되어 있으므로, 일곱 개 모두 5가 됩니다. 두 개의 0은 다른 색이므로 그대로 유지됩니다.
- 입력
- image = [[3, 3, 3], [3, 7, 3], [3, 3, 3]]sr = 1sc = 1color = 7
- 출력
- [[3, 3, 3], [3, 7, 3], [3, 3, 3]]
- 설명
- 시작 부분은 이미 색상 7이므로 해당 영역을 7로 칠해도 아무것도 바뀌지 않습니다. 이미지는 원래대로 돌아오고, 3으로 된 고리는 다른 색상이므로 그대로 유지됩니다.
- 입력
- image = [[2, 2, 4, 4], [4, 2, 2, 4], [4, 4, 2, 2]]sr = 2sc = 3color = 9
- 출력
- [[9, 9, 4, 4], [4, 9, 9, 4], [4, 4, 9, 9]]
- 설명
- 2는 오른쪽 아래 모서리에서 왼쪽 위까지 계단 모양을 이루며, 각 계단은 다음 계단과 한 변을 공유하므로 2 여섯 개가 모두 9로 바뀝니다. 4는 서로 분리된 두 개의 영역으로 나뉘며 색을 그대로 유지합니다.
제출 시 숨은 테스트 +18개
후속 질문
모서리에서만 맞닿은 픽셀도 연결된 것으로 간주한다면, 해법은 어떻게 달라질까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
어떤 픽셀을 변경할 수 있을까요? 시작 픽셀과 색이 같고, 같은 색의 경로로 시작 픽셀과 연결된 픽셀만 변경할 수 있습니다.
각 픽셀을 노드로 보고, 두 픽셀이 한 변을 공유하며 둘 다 시작 색상일 때 연결하세요. 영역은 시작점에서 도달할 수 있는 모든 것이므로, 그래프 탐색을 사용하면 영역을 찾을 수 있습니다.
아직 확인하지 않은 픽셀을 스택에 쌓아 두세요. 픽셀을 스택에 넣는 순간 색칠하면, 색칠된 픽셀은 더 이상 조건에 맞지 않으므로 다시는 스택에 넣지 않습니다. 새 색상이 기존 색상과 같은지 먼저 확인하세요.
풀이
영역은 그래프에서 연결된 부분입니다. 픽셀은 노드이며, 시작 색상이 같고 변을 공유하는 두 픽셀은 연결됩니다. 주어진 픽셀에서 시작해 해당 색상만 따라 이동하는 검색은 영역 전체를 찾습니다. 주의할 점은 새 색상이 기존 색상과 같은 이미지와 재귀 검색을 중단시킬 수 있는 길고 구불구불한 영역입니다.
재귀적 깊이 우선 탐색
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
작은 작업 하나만 수행하는 함수 paint(r, c)를 작성하세요. 픽셀이 이미지 안에 있고 아직 이전 색이라면 새 색으로 칠한 다음 네 이웃 픽셀에서 함수를 호출합니다. 시작 픽셀에서 한 번 호출하면 영역 전체로 퍼집니다. 영역의 모든 픽셀은 이전 색 픽셀로 이루어진 경로를 통해 시작 픽셀과 연결되어 있고, 호출이 그 경로를 따라가기 때문입니다.
네 번의 호출 전에 픽셀을 칠하면 색칠이 빙빙 도는 것을 막을 수 있습니다. 이웃 픽셀이 다시 색칠된 픽셀을 호출하면 색이 더 이상 일치하지 않으므로 호출은 즉시 반환됩니다. 이 방법은 새 색이 이전 색과 다를 때만 작동하므로, 먼저 확인하고 두 색이 같으면 이미지를 변경하지 않은 채 반환하세요.
작업량은 O(m × n)이지만, 호출 스택이 취약점입니다. 재귀는 따라가는 경로만큼 깊어집니다. 80 × 80 이미지에서 폭이 1픽셀인 뱀 모양 경로의 길이는 약 3,200픽셀이므로 호출이 약 3,200단계까지 중첩됩니다. Python은 기본적으로 1,000단계에서 멈추고 오류를 발생시키므로, 이 접근 방식은 가장 큰 테스트를 통과하지 못합니다. 다른 언어에서는 더 깊은 호출을 허용하지만, 이미지가 더 커지면 그 언어들도 호출 스택이 고갈됩니다.
알고리즘
old = image[sr][sc]을 읽습니다.old가color와 같으면 이미지를 반환합니다.paint(r, c)를 정의합니다.(r, c)가 이미지 범위 밖에 있거나 해당 색상이old가 아니면 반환합니다.- 그렇지 않으면
image[r][c] = color로 설정하고 위, 아래, 왼쪽, 오른쪽 픽셀에 대해paint를 호출합니다. paint(sr, sc)를 호출하고 이미지를 반환합니다.
def floodFill(image, sr, sc, color):
old = image[sr][sc]
if old == color:
return image
rows, cols = len(image), len(image[0])
def paint(r, c):
# Stop outside the image and at any pixel that is not the old color.
if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
return
image[r][c] = color
paint(r + 1, c)
paint(r - 1, c)
paint(r, c + 1)
paint(r, c - 1)
paint(sr, sc)
return image명시적 스택을 사용한 깊이 우선 탐색
핵심 아이디어
같은 탐색을 하되, 방문할 픽셀을 호출 스택이 아닌 직접 관리하는 스택에 보관하세요. 시작 픽셀을 칠하고 스택에 넣으세요. 픽셀을 하나 꺼내 네 이웃을 살펴본 다음, 이미지 안에 있고 여전히 이전 색상인 각 이웃을 칠해 스택에 넣으세요. 스택이 비면 영역 전체를 칠한 것입니다.
픽셀을 꺼낼 때가 아니라 스택에 넣을 때 칠하세요. 칠해진 픽셀은 더 이상 이전 색상이 아니므로, 색상 확인이 방문 여부 확인도 겸합니다. 따라서 어떤 픽셀도 스택에 두 번 들어가지 않으며, 별도의 표시 격자가 필요하지 않습니다. 재귀 버전과 마찬가지로 새 색상은 이전 색상과 달라야 하므로, 두 색상이 같으면 이미지를 변경하지 않고 반환하세요.
영역의 각 픽셀은 한 번씩 스택에 들어가고 네 이웃을 확인하므로, 시간 복잡도는 O(m × n)입니다. 스택에는 영역의 픽셀을 최대한 담습니다. 스택은 일반 메모리에 있으므로, 재귀 버전에서는 호출 스택이 부족했던 3,200픽셀의 구불구불한 영역도 문제없습니다.
알고리즘
old = image[sr][sc]를 읽습니다.old가color와 같으면 이미지를 반환합니다.(sr, sc)를 칠하고 스택에 넣습니다.- 픽셀을 꺼내 네 방향의 이웃을 살펴봅니다.
- 이미지 안에 있고 색이
old인 각 이웃을 칠하고 스택에 넣습니다. - 스택이 비면 이미지를 반환합니다.
def floodFill(image, sr, sc, color):
old = image[sr][sc]
# Painting a region its own color changes nothing. Returning here also
# stops the search from pushing the same cells forever.
if old == color:
return image
rows, cols = len(image), len(image[0])
image[sr][sc] = color
stack = [(sr, sc)]
while stack:
r, c = stack.pop()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
# Paint on push: a painted cell no longer matches old,
# so it can never be pushed twice.
image[nr][nc] = color
stack.append((nr, nc))
return image
함정과 경계 사례
대부분의 오답은 같은 색인 경우를 처리하지 않거나, 이미지 범위를 벗어나거나, 긴 영역에서 재귀를 사용하기 때문에 발생합니다.
color가 시작 색과 같은 경우를 잊는 것. 이때 칠해도 아무것도 바뀌지 않으므로, 색을 방문 표시로 사용하는 탐색은 같은 픽셀을 무한히 추가합니다.- 칠한 뒤에
image[sr][sc]를 읽는 것. 기존 색을 먼저 저장하세요. 그렇지 않으면 모든 이웃을 새 색과 비교하게 됩니다. - 대각선 이웃을 세는 것. 모서리만 맞닿은 픽셀은 연결되어 있지 않습니다.
- 이미지 범위 안에 있는지 확인하기 전에 이웃의 색을 확인하는 것. 먼저
0 ≤ row < rows와0 ≤ col < cols를 검사하세요. - 큰 이미지에서 재귀를 사용하는 것. 80 × 80 이미지에서 너비가 1픽셀인 경로는 길이가 약 3,200픽셀이므로, Python의 재귀 한도를 넘기에 충분히 깊습니다.
- 이미지 전체에서 기존 색인 모든 픽셀을 칠하는 것. 시작점과 연결되지 않은 같은 색의 픽셀은 색을 그대로 유지해야 합니다.
자주 묻는 질문4
Flood Fill의 시간 복잡도는 얼마인가요?
행이 m개, 열이 n개인 이미지의 경우 O(m × n)입니다. 영역의 각 픽셀은 스택에 한 번 푸시되고 네 개의 이웃을 살펴보며, 영역 바깥의 픽셀은 이웃으로서만 살펴봅니다. 이미지 전체가 하나의 영역이면 스택에 최대 m × n개의 픽셀이 들어갈 수 있습니다.
Flood Fill에는 BFS와 DFS 중 무엇을 사용해야 할까요?
둘 다 작동하며 시간 복잡도는 O(m × n)입니다. 어떤 순서로 방문하든 영역은 동일하므로, 큐(너비 우선)와 스택(깊이 우선)은 같은 픽셀을 채색합니다. 사용하는 언어에서 작성하기 더 짧은 쪽을 선택하고, 큰 이미지에서는 재귀를 피하세요.
새 색이 이전 색과 같으면 Flood Fill은 왜 무한 루프에 빠지나요?
일반적인 해결 방법은 "아직 이전 색상이다"를 "아직 방문하지 않았다"로 간주합니다. 새 색상이 이전 색상과 같으면 픽셀을 칠해도 바뀌지 않으므로, 이웃 픽셀들이 해당 픽셀을 다시 스택에 넣고 탐색은 끝나지 않습니다. 이 경우를 먼저 확인하고 이미지를 반환하면 문제가 해결되며, 변경되지 않은 이미지가 올바른 답입니다.
Flood Fill을 재귀적으로 해결할 수 있나요?
네, 픽셀을 칠하고 이전 색상의 각 이웃에서 자신을 호출하는 함수는 올바릅니다. 위험 요소는 깊이입니다. 재귀는 검색이 따라가는 가장 긴 경로만큼 깊어지며, 구불구불한 영역에서는 호출 횟수가 수천 번에 이를 수 있습니다. 명시적 스택을 사용하면 이러한 제한 없이 같은 작업을 수행할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def floodFill(image, sr, sc, color):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]] sr = 0 sc = 0 color = 5
기대값
[[5, 5, 0], [5, 0, 5], [5, 5, 5]]