DFS: 연결 요소와 플러드 필
DFS를 적용해 연결 요소를 세고, 2차원 격자의 number-of-islands를 해결하며, 이미지 처리를 위한 플러드 필을 구현합니다.
DFS: 연결 요소와 플러드 필은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
연결 요소의 정의
무방향 그래프의 연결 요소는 그 집합의 모든 정점 쌍 사이에 경로가 존재하는 최대 정점 집합입니다. 하나의 그래프에 서로 연결되지 않은 요소가 여러 개 있을 수 있습니다. 연결 요소 찾기는 많은 그래프 문제의 기초입니다. 그룹화, 병합, 섬 개수 세기, 계정 통합은 모두 이 기본 작업으로 해결할 수 있습니다.
from collections import defaultdict
# Graph with 3 components: {0,1,2}, {3,4}, {5}
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,2),(3,4)]:
graph[u].append(v)
graph[v].append(u)
# Node 5 is isolated (no edges)
for node in [0,1,2,3,4,5]:
if node not in graph:
graph[node] = []
# We need DFS or BFS from each unvisited node
# to discover all components
print('Graph has nodes 0-5 with components: {0,1,2}, {3,4}, {5}')DFS로 연결 요소 개수 세기
모든 노드를 순회합니다. 방문하지 않은 노드마다 DFS를 시작하여 도달 가능한 모든 노드를 방문한 것으로 표시합니다. DFS를 시작할 때마다 새로운 요소 하나를 발견한 것입니다. DFS를 시작한 횟수를 세면 요소의 개수를 구할 수 있습니다. 이 O(V + E) 알고리즘은 그래프가 연결되어 있든 아니든 올바르게 작동합니다.
from collections import defaultdict
def count_components(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
def dfs(node):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs(nb)
for node in range(n):
if node not in visited:
dfs(node)
count += 1
return count
print(count_components(6, [(0,1),(0,2),(1,2),(3,4)])) # 3
print(count_components(5, [(0,1),(1,2),(3,4)])) # 2섬의 개수
섬의 개수(LeetCode #200)는 2차원 격자에서 연결 요소를 찾는 대표적인 문제입니다. 각 ‘1’ 셀은 섬에 속하며, 인접한 ‘1’ 셀(위/아래/왼쪽/오른쪽)은 같은 섬을 이룹니다. DFS를 사용해 서로 다른 섬의 개수를 셉니다. 모든 셀을 순회하면서 방문하지 않은 ‘1’을 발견하면 연결된 모든 ‘1’ 셀을 표시하는 DFS(영역 채우기)를 시작하고, 그 후 개수를 1 증가시킵니다.
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != '1':
return
grid[r][c] = '#' # mark visited in-place
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
grid = [['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']]
print(num_islands(grid)) # 3영역 채우기 알고리즘
영역 채우기(LeetCode #733)는 주어진 시작 색상과 연결된 모든 셀을 새 색상으로 바꿉니다. 이미지 편집기의 페인트 통 도구와 같은 기능입니다. DFS를 사용하여 시작 픽셀에서 출발해 원래 색상과 일치하는 모든 이웃의 색상을 재귀적으로 변경합니다. 중요한 예외 상황은 시작 셀의 색상이 이미 새 색상과 같은 경우입니다. 무한 재귀를 피하려면 즉시 반환해야 합니다.
def flood_fill(image, sr, sc, new_color):
original = image[sr][sc]
if original == new_color:
return image # edge case: same color, nothing to do
rows, cols = len(image), len(image[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != original:
return
image[r][c] = new_color
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
dfs(sr, sc)
return image
image = [[1,1,1],[1,1,0],[1,0,1]]
result = flood_fill(image, 1, 1, 2)
for row in result: print(row)
# [[2,2,2],[2,2,0],[2,0,1]]섬의 최대 넓이
섬의 최대 넓이 (LeetCode #695)는 섬 개수 세기를 확장한 문제로, 각 섬에 대해 가장 큰 섬의 크기를 반환합니다. DFS 플러드 필 중 표시하는 칸의 수를 셉니다. DFS는 현재 섬의 크기를 반환하고, 모든 섬에서 얻은 최댓값을 추적합니다. 이는 연결 요소 패턴을 간단히 확장한 것입니다.
def max_area_of_island(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
max_area = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return 0
if grid[r][c] != 1:
return 0
grid[r][c] = 0 # mark visited
return (1 + dfs(r+1,c) + dfs(r-1,c) +
dfs(r,c+1) + dfs(r,c-1))
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
max_area = max(max_area, dfs(r, c))
return max_area
grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0]]
print(max_area_of_island(grid)) # 6태평양과 대서양으로 흐르는 물
태평양과 대서양으로 흐르는 물 (LeetCode #417)은 어느 칸에서 물이 태평양(위쪽/왼쪽 가장자리)과 대서양(아래쪽/오른쪽 가장자리) 양쪽으로 흐를 수 있는지 묻습니다. 아래쪽으로 흐르는 물을 시뮬레이션하는 대신 역방향 DFS를 사용합니다. 즉, 바다에서 물이 위쪽으로 흐른다고 생각합니다. 태평양 경계에서 한 번, 대서양 경계에서 한 번씩 DFS를 수행하여 도달 가능한 칸을 모읍니다. 두 결과의 교집합이 답입니다.
def pacific_atlantic(heights):
rows, cols = len(heights), len(heights[0])
pac = set(); atl = set()
def dfs(r, c, visited, prev_h):
if (r,c) in visited or r < 0 or r >= rows or c < 0 or c >= cols:
return
if heights[r][c] < prev_h:
return # water can't flow uphill in reverse
visited.add((r,c))
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r+dr, c+dc, visited, heights[r][c])
for r in range(rows):
dfs(r, 0, pac, heights[r][0]) # Pacific left
dfs(r, cols-1, atl, heights[r][cols-1]) # Atlantic right
for c in range(cols):
dfs(0, c, pac, heights[0][c]) # Pacific top
dfs(rows-1, c, atl, heights[rows-1][c]) # Atlantic bottom
return sorted(pac & atl) # intersection
print(pacific_atlantic([[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]))연결 요소를 위한 반복 DFS
큰 격자에서 파이썬의 재귀 제한을 피하려면 반복 DFS(명시적 스택 사용)를 사용합니다. 반복 버전은 재귀 DFS와 동등하지만 호출 스택 대신 스택을 사용합니다. 시작 노드를 스택에 넣고, 꺼낸 뒤 방문한 것으로 표시하고, 방문하지 않은 이웃을 스택에 넣습니다. 이렇게 하면 재귀 DFS에서 스택 오버플로가 발생할 수 있는 수백만 개의 칸으로 이루어진 격자도 안전하게 처리할 수 있습니다.
def count_components_iterative(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
for start in range(n):
if start in visited:
continue
# Iterative DFS
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for nb in graph[node]:
if nb not in visited:
stack.append(nb)
count += 1
return count
print(count_components_iterative(6, [(0,1),(0,2),(1,2),(3,4)])) # 3둘러싸인 영역
둘러싸인 영역 (LeetCode #130)은 'X' 경계에 완전히 둘러싸인 모든 'O' 영역을 찾습니다. 'O' 칸 중 하나라도 보드 가장자리에 닿으면 해당 영역은 NOT 포착됩니다. 핵심은 둘러싸인 영역을 직접 찾는 대신, 모든 경계의 'O' 칸에서 DFS를 수행하고 도달 가능한 모든 칸을 안전한 것으로 표시하는 것입니다. 그런 다음 뒤집습니다. 남은 모든 'O' 칸은 둘러싸인 영역이므로 'X'로 바꾸고, 안전한 칸은 다시 'O'로 복원합니다.
def solve(board):
if not board:
return
rows, cols = len(board), len(board[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if board[r][c] != 'O':
return
board[r][c] = 'S' # safe: connected to border
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
# Mark border-connected O's as safe
for r in range(rows):
dfs(r, 0); dfs(r, cols-1)
for c in range(cols):
dfs(0, c); dfs(rows-1, c)
# Flip: surrounded O -> X, safe S -> O
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O': board[r][c] = 'X'
elif board[r][c] == 'S': board[r][c] = 'O'
board = [['X','X','X','X'],['X','O','O','X'],
['X','X','O','X'],['X','O','X','X']]
solve(board)
print([board[1][1], board[3][1]]) # X, O부분 섬 세기
부분 섬 세기 (LeetCode #1905)는 두 번째 격자의 섬 중 첫 번째 격자의 섬 안에 완전히 포함된 섬을 찾습니다. 두 번째 격자의 각 '1' 칸에서 DFS를 시작합니다. 방문하는 모든 칸이 첫 번째 격자에서도 '1'이면 해당 섬은 부분 섬입니다. 핵심은 섬의 모든(ALL) 칸을 방문해 탐색한 것으로 표시하면서, 그 칸들이 첫 번째 격자에서도 모두 '1'인지 추적하는 것입니다. 첫 번째 격자에서 처음 '0'을 만났다고 해서 일찍 중단하지 마십시오. 그러면 같은 섬의 다른 칸을 표시하지 못하게 됩니다.
def count_sub_islands(grid1, grid2):
rows, cols = len(grid2), len(grid2[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return True
if grid2[r][c] != 1:
return True
grid2[r][c] = 0 # mark visited
is_sub = grid1[r][c] == 1 # this cell must be in grid1
is_sub = dfs(r+1,c) and is_sub # note: AND not short-circuit OR
is_sub = dfs(r-1,c) and is_sub
is_sub = dfs(r,c+1) and is_sub
is_sub = dfs(r,c-1) and is_sub
return is_sub
count = 0
for r in range(rows):
for c in range(cols):
if grid2[r][c] == 1 and dfs(r, c):
count += 1
return count
print(count_sub_islands([[1,1,1],[1,0,1],[1,1,1]],
[[1,1,1],[1,0,1],[1,1,1]])) # 1연결 요소를 위한 DFS와 BFS 비교
DFS와 BFS는 모두 연결된 모든 요소를 정확히 찾으며, 시간 복잡도는 O(V + E), 공간 복잡도는 O(V)로 같습니다. 연결 요소 문제에서는 재귀적으로 구현하기 쉬운 DFS가 더 간단하고, 최단 경로 정보도 필요할 때는 BFS를 선호합니다. 격자 문제에서는 DFS가 한 방향으로 깊이 탐색한 뒤 되돌아오므로 캐시 친화적이며, 가까운 메모리 위치에 순차적으로 접근합니다.
# DFS advantages for connected components:
# - Simpler recursive implementation
# - Lower constant factor for small graphs
# - Can restore grid state during backtracking (if needed)
# BFS advantages:
# - Finds shortest path while traversing
# - Better for wide, shallow graphs (avoids deep recursion)
# - Multi-source initialisation is natural
# Same asymptotic complexity: O(V + E) time, O(V) space
# Grid (m rows, n cols): O(mn) time and space
print('DFS and BFS: same O(V+E) complexity for component counting')제약이 있는 섬: 모양과 둘레
섬의 둘레 (LeetCode #463)는 격자에 있는 하나의 섬 전체의 둘레를 셉니다. 각 육지 칸('1')에 대해 둘레에 4를 add한 다음, 인접한 육지 칸마다 2를 뺍니다(공유하는 변 때문입니다). 이 O(mn) 공식 기반 접근법에는 DFS가 필요하지 않습니다. 하지만 경계 변을 세는 DFS와 동등하다는 점을 이해하면 격자 문제와 그래프적 사고의 연결을 더욱 분명히 알 수 있습니다.
def island_perimeter(grid):
rows, cols = len(grid), len(grid[0])
perimeter = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
perimeter += 4 # start with 4 sides
# Subtract shared edges with adjacent land cells
if r > 0 and grid[r-1][c] == 1:
perimeter -= 2 # shared top edge
if c > 0 and grid[r][c-1] == 1:
perimeter -= 2 # shared left edge
return perimeter
grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
print(island_perimeter(grid)) # 16빠른 확인
이 레슨에서 다룬 자료 구조 및 알고리즘 & 코딩 면접 대비 개념에 대한 이해도를 확인합니다.
학습 내용 요약
이번 레슨에서는 방문 표시를 추적하는 DFS를 통한 연결 요소, 대표적인 2차원 격자 응용인 섬 개수 세기와 플러드 필, 그리고 경계에서 시작하는 역방향 DFS(둘러싸인 영역)와 제약 조건을 추적하는 다중 DFS(부분 섬) 같은 고급 패턴을 배웠습니다. 다음에는 방향 그래프와 무방향 그래프에서의 사이클 탐지를 살펴봅니다.
자주 묻는 질문
“DFS: 연결 요소와 플러드 필” 강의는 무료인가요?
네 — “DFS: 연결 요소와 플러드 필” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“DFS: 연결 요소와 플러드 필”에서 뭘 배우나요?
DFS를 적용해 연결 요소를 세고, 2차원 격자의 number-of-islands를 해결하며, 이미지 처리를 위한 플러드 필을 구현합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“DFS: 연결 요소와 플러드 필” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 그래프 표현과 순회 설정
- BFS: 최단 경로와 레벨 순회
- DFS: 연결 요소와 플러드 필
- 방향 그래프와 무방향 그래프의 순환 탐지