섬의 개수 - DFS vs BFS로 탐색 알고리즘 비교하기
깊이 들어갈 것인가, 넓게 펼칠 것인가?
🏝️ 문제 소개: 섬의 개수를 세는 방법
"섬의 개수"는 백준 온라인 저지의 대표적인 DFS/BFS 문제다.
지도는 바다(0)와 땅(1)으로 이루어진 2차원 그리드이며, 서로 연결된 1의 집합을 하나의 섬으로 본다. 이때 연결은 상하좌우 + 대각선 총 8방향으로 이루어진다. 목표는 지도에서 총 몇 개의 섬이 있는지 세는 것이다.
예시 입력
5 4
1 1 1 1 0
1 1 0 0 0
1 0 0 1 1
0 0 0 1 1
출력
2
🔍 탐색 방법의 핵심: DFS vs BFS
이 문제의 핵심은 탐색(Traversal) 이다. 땅(1)을 발견했을 때, 연결된 모든 땅을 순회하며 방문 처리하고 하나의 섬으로 세는 방식이다.
여기에는 두 가지 접근 방식이 있다.
- DFS (Depth-First Search) - 깊이 우선 탐색
- BFS (Breadth-First Search) - 너비 우선 탐색
🧠 DFS로 풀이하기
DFS는 "한 방향으로 깊게 들어가는" 방식의 탐색이다. 일반적으로 재귀를 사용하지만, 파이썬에서는 재귀 깊이 제한 때문에 반복문 + 스택으로 구현하는 경우도 많다.
dx = [1, 1, 0, -1, -1, -1, 0, 1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
while True:
w, h = map(int, input().split())
if w == 0 and h == 0:
break
grid = [list(map(int, input().split())) for _ in range(h)]
visited = [[False]*w for _ in range(h)]
def dfs(x, y):
stack = [(x, y)]
visited[x][y] = True
while stack:
cx, cy = stack.pop()
for d in range(8):
nx, ny = cx + dx[d], cy + dy[d]
if 0 <= nx < h and 0 <= ny < w:
if grid[nx][ny] == 1 and not visited[nx][ny]:
visited[nx][ny] = True
stack.append((nx, ny))
island_count = 0
for i in range(h):
for j in range(w):
if grid[i][j] == 1 and not visited[i][j]:
dfs(i, j)
island_count += 1
print(island_count)
- 땅(1)을 발견하면, 스택에 넣고 방문 체크
- 스택이 빌 때까지 8방향 탐색을 반복
- 연결된 땅을 모두 방문하고 나면 섬 하나를 탐색 완료한 것이므로 개수 증가
🚶 BFS로 풀이하기
BFS는 "가까운 곳부터 탐색하는" 방식이다. DFS와 달리 큐(Queue) 를 사용하며, 시작점에서 점점 바깥으로 퍼져 나간다.
from collections import deque
dx = [1, 1, 0, -1, -1, -1, 0, 1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
while True:
w, h = map(int, input().split())
if w == 0 and h == 0:
break
grid = [list(map(int, input().split())) for _ in range(h)]
visited = [[False]*w for _ in range(h)]
def bfs(x, y):
queue = deque([(x, y)])
visited[x][y] = True
while queue:
cx, cy = queue.popleft()
for d in range(8):
nx, ny = cx + dx[d], cy + dy[d]
if 0 <= nx < h and 0 <= ny < w:
if grid[nx][ny] == 1 and not visited[nx][ny]:
visited[nx][ny] = True
queue.append((nx, ny))
island_count = 0
for i in range(h):
for j in range(w):
if grid[i][j] == 1 and not visited[i][j]:
bfs(i, j)
island_count += 1
print(island_count)
- 땅을 발견하면 큐에 넣고 방문 처리
- 큐에서 하나씩 꺼내며 8방향을 탐색
- 큐에 넣는 순서대로 퍼져나가기 때문에 한 층씩 넓어지는 탐색 방식
🧭 DFS vs BFS 비교
| 자료구조 | 스택(또는 재귀) | 큐 |
| 탐색 방식 | 깊이 우선 | 너비 우선 |
| 코드 간결성 | 재귀로 간단 | 반복문 기반 |
| 재귀 깊이 이슈 | 있음 | 없음 |
| 메모리 사용 | 상대적으로 적음 | 큐에 노드가 많이 쌓일 수 있음 |
재귀 제한이 있는 환경에서는 BFS가 더 안정적인 선택이 될 수 있다!
🔎 탐색 순서 시각화
다음은 5x4 격자에서 DFS와 BFS의 방문 순서를 시각화한 예시이다.
1 1 1 1 1
1 1 1 1 1
1 1 0 0 0
1 1 0 1 1
DFS 방문 순서
1 2 5 8 13
4 3 6 9 14
7 10 * * *
16 11 * 12 15
BFS 방문 순서
1 2 5 8 11
3 4 6 9 12
7 10 * * *
13 14 * 15 16
💡 왜 DFS는 방향이 자주 바뀌는가?
DFS는 스택 기반이라 가장 최근에 들어온 노드부터 탐색한다. 따라서 막다른 길에 도달하면 스택에서 빠져나와 역방향으로 튀는 현상이 발생한다.
반면 BFS는 큐에 쌓인 순서대로 탐색되므로, 방향 전환이 덜하며 방향성이 일정하고 계단식 탐색이 가능하다.
⏱️ 탐색 순서에 따른 시간 복잡도 차이
DFS와 BFS는 그래프의 모든 노드를 방문한다는 점에서 기본적으로 시간 복잡도는 동일하다. 둘 다 O(V+E) 시간이 소요된다.
(V: 정점 수, E: 간선 수)
하지만 실제 알고리즘 수행 시 몇 가지 차이점이 있다.
• DFS는 경로의 특성상 목표 노드가 깊은 곳에 있을 때 빠르게 도달할 수 있다
• BFS는 최단 경로를 찾는 데 유리하며, 가까운 해결책부터 발견한다
• 그리드 탐색에서는 두 알고리즘 모두 대부분의 경우 O(N*M)의 시간 복잡도를 가진다
🎯 실제 문제에서 DFS/BFS 선택 기준
알고리즘을 선택할 때는 문제의 특성을 고려해야 한다.
여기서 주목할 점은 그래프의 특성에 따라 어떤 알고리즘이 더 효율적일 수 있다는 것이다.
DFS가 유리한 경우
- 경로의 존재 여부만 확인하는 문제
- 백트래킹이 필요한 문제 (ex: 미로 탈출, 단어 찾기)
- 그래프의 사이클 탐지
- 위상 정렬
BFS가 유리한 경우
- 최단 경로 문제 (ex: 최소 이동 횟수)
- 레벨 단위로 탐색이 필요한 문제
- 두 노드 사이의 최소 거리
- 그래프의 연결 요소 찾기
"섬의 개수" 문제는 단순히 연결된 요소를 찾는 것이라 두 알고리즘 모두 적합하다. 개인 취향과 구현 편의성에 따라 선택하면 된다! 코테 결과는.. .어... 몰라
🔄 재귀 DFS와 스택 DFS의 비교
DFS는 재귀로도, 스택으로도 구현할 수 있다. 두 방식은 동일한 기능을 하지만 몇 가지 차이점이 있다.
# 재귀 DFS
def recursive_dfs(x, y):
visited[x][y] = True
for d in range(8):
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < h and 0 <= ny < w:
if grid[nx][ny] == 1 and not visited[nx][ny]:
recursive_dfs(nx, ny)
# 스택 DFS (위에서 제시한 방식)
def stack_dfs(x, y):
stack = [(x, y)]
visited[x][y] = True
while stack:
cx, cy = stack.pop()
for d in range(8):
nx, ny = cx + dx[d], cy + dy[d]
if 0 <= nx < h and 0 <= ny < w:
if grid[nx][ny] == 1 and not visited[nx][ny]:
visited[nx][ny] = True
stack.append((nx, ny))
주요 차이점
특성 재귀 DFS 스택 DFS
| 구현 난이도 | 간결하고 직관적 | 약간 복잡함 |
| 호출 스택 오버플로우 | 발생 가능성 있음 | 발생하지 않음 |
| 메모리 사용 | 시스템 스택 사용 | 명시적 스택 사용 |
| 탐색 순서 | 일정함 | 일정함 |
| 디버깅 | 비교적 어려움 | 비교적 쉬움 |
파이썬은 재귀 호출에 기본 제한(1000)이 있어서 큰 그래프에서는 스택 기반 DFS가 더 안전하다.
마무리
"섬의 개수" 문제는 그래프 탐색의 기본을 익히는 좋은 시작점이다. DFS와 BFS 둘 다 효과적으로 해결할 수 있으며, 각 알고리즘의 특성을 이해하면 더 복잡한 문제로 나아갈 때 큰 도움이 될 것이다.
다른 유사 문제로는 "적록색약", "치즈", "미로 탐색" 등이 있으니 함께 풀어보며 탐색 알고리즘의 감각을 키워봅시닷다라