3강. DFS & BFS
📌 탐색 알고리즘이란?
많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
대표적인 그래프 탐색 알고리즘으로 DFS와 BFS가 있으며, 코딩 테스트에서 매우 자주 등장하므로 반드시 숙지해야 한다.
🗂️ 자료구조 기본기
스택 (Stack)
- 선입후출 (LIFO) — 나중에 들어온 것이 먼저 나온다.
- Python에서는 리스트의
append()/pop()으로 구현한다.
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop() # 7 제거
stack.append(1)
stack.append(4)
stack.pop() # 4 제거
print(stack[::-1]) # 최상단 원소부터 출력: [1, 3, 2, 5]
print(stack) # 최하단 원소부터 출력: [5, 2, 3, 1]큐 (Queue)
- 선입선출 (FIFO) — 먼저 들어온 것이 먼저 나온다.
- Python에서는
collections.deque를 사용한다. (리스트보다 효율적)
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft() # 5 제거
queue.append(1)
queue.append(4)
queue.popleft() # 2 제거
print(queue) # 먼저 들어온 순서대로: deque([3, 7, 1, 4])
queue.reverse()
print(queue) # 나중에 들어온 원소부터: deque([4, 1, 7, 3])🔄 재귀 함수
자기 자신을 다시 호출하는 함수
종료 조건이 반드시 필요하다
종료 조건 없이 재귀를 호출하면 최대 재귀 깊이를 초과해 에러가 발생한다.
def recursive_function(i):
if i == 100: # 종료 조건
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
recursive_function(i + 1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)팩토리얼 비교 예시
# 반복문으로 구현
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
# 재귀로 구현
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n - 1)
print('반복적으로 구현:', factorial_iterative(5)) # 120
print('재귀적으로 구현:', factorial_recursive(5)) # 120유클리드 호제법 (최대공약수)
A를 B로 나눈 나머지를 R이라 할 때, GCD(A, B) = GCD(B, R)
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162)) # 6재귀 함수 유의사항
- 복잡한 알고리즘을 간결하게 작성할 수 있지만, 가독성이 떨어질 수 있다.
- 모든 재귀 함수는 반복문으로 동일하게 구현 가능하다.
- 함수 호출 시 스택 프레임에 쌓이기 때문에, 스택이 필요한 경우 재귀로 대체하는 경우가 많다.
🔍 DFS (깊이 우선 탐색)
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
- 스택 최상단 노드에 방문하지 않은 인접 노드가 있으면 → 스택에 넣고 방문 처리
- 방문하지 않은 인접 노드가 없으면 → 스택에서 최상단 노드를 꺼낸다.
- 더 이상 반복할 수 없을 때까지 2~3을 반복한다.
핵심
- 스택 또는 재귀 함수를 이용한다.
- 실제 구현에서는 재귀 함수가 더 간결하다.
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[],
[2, 3, 8], # 1번 노드와 연결
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
dfs(graph, 1, visited)
# 출력: 1 2 7 6 8 3 4 5🔍 BFS (너비 우선 탐색)
그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
- 큐에서 노드를 꺼낸 뒤, 인접한 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 더 이상 반복할 수 없을 때까지 2를 반복한다.
핵심
- 큐 자료구조를 이용한다.
- 최단 거리 문제에 유리하다. (모든 간선의 비용이 동일할 때)
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
bfs(graph, 1, visited)
# 출력: 1 2 3 8 7 4 5 6🆚 DFS vs BFS 비교
| 구분 | DFS | BFS |
|---|---|---|
| 자료구조 | 스택 / 재귀 | 큐 |
| 탐색 방식 | 깊이 우선 | 너비 우선 |
| 최단 거리 | ❌ 보장 안 됨 | ✅ 보장됨 (비용 동일 시) |
| 주요 활용 | 연결 요소 개수, 사이클 탐지 | 최단 경로, 레벨 탐색 |
🧊 문제 1. 음료수 얼려 먹기
문제
N×M 얼음 틀에서 0은 구멍, 1은 칸막이다. 상하좌우로 연결된 0끼리 하나의 아이스크림이 된다. 총 아이스크림의 개수를 구하라.
아이디어 (DFS)
- 모든 칸을 순서대로 확인하며
0인 칸에서 DFS를 수행한다. - DFS 중에 방문한
0칸을1로 바꿔 재방문을 방지한다. - DFS가 한 번 성공할 때마다 아이스크림 개수를 +1 한다.
def dfs(x, y):
# 범위를 벗어나면 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
if graph[x][y] == 0:
graph[x][y] = 1 # 방문 처리
dfs(x - 1, y)
dfs(x + 1, y)
dfs(x, y - 1)
dfs(x, y + 1)
return True
return False
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
result = 0
for i in range(n):
for j in range(m):
if dfs(i, j) == True:
result += 1
print(result)
# 입력 예시:
# 4 5
# 00110
# 00011
# 11111
# 00000
# 출력: 3핵심 포인트
graph[x][y] = 1로 방문을 표시해 별도의visited배열 없이도 동작한다.- 범위 체크를 먼저 하는 것이 핵심 — 범위 밖이면
False를 반환하고 종료한다.
🌀 문제 2. 미로 탈출
문제
N×M 미로에서 (1,1)에서 출발해 (N,M)까지 이동할 때, 최소 칸의 개수를 구하라. 0은 괴물(이동 불가), 1은 이동 가능한 칸이다.
아이디어 (BFS)
- BFS는 가까운 노드부터 탐색하므로 최단 경로를 보장한다.
- 방문할 때마다 이전 칸의 거리 + 1을 기록한다.
- 별도의 거리 배열 없이 graph 값 자체를 거리로 갱신한다.
from collections import deque
def bfs(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if graph[nx][ny] == 0: # 벽이면 무시
continue
if graph[nx][ny] == 1: # 처음 방문하는 경우만 기록
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
return graph[n - 1][m - 1]
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
print(bfs(0, 0))
# 입력 예시:
# 3 3
# 110
# 010
# 011
# 출력: 5핵심 포인트
graph[nx][ny] == 1조건으로 처음 방문하는 칸만 거리를 갱신한다.- 이미 거리가 기록된 칸(값 > 1)은 다시 큐에 넣지 않아 중복 탐색을 방지한다.
graph[n-1][m-1]을 반환하면 자연스럽게 최단 거리가 나온다.
📝 정리
| 문제 유형 | 알고리즘 | 이유 |
|---|---|---|
| 연결된 구역의 개수 | DFS | 연결 요소 탐색에 적합 |
| 최단 경로 / 최소 칸 | BFS | 가까운 노드부터 탐색해 최단 거리 보장 |
