코딩 테스트에서 DFS와 BFS 문제를 만났을 때 바로 꺼내 쓸 수 있는 **'표준 템플릿'**을 정리해 드릴게요. 이 구조만 완벽히 외우면, 문제의 조건(상하좌우 이동, 연결 리스트 등)에 따라 내부 로직만 살짝 수정해서 모든 문제에 대응할 수 있습니다.
1. BFS 템플릿 (최단 거리, 최소 횟수)
BFS는 **큐(Queue)**를 사용하며, "현재 위치에서 갈 수 있는 곳을 다 넣는다"는 개념만 기억하세요.
Python
from collections import deque
def bfs(start_node, graph, n):
queue = deque([start_node])
visited = [False] * (n + 1) # 보통 노드 번호가 1부터 시작하므로 n+1
visited[start_node] = True
while queue:
curr = queue.popleft()
# 현재 노드(curr)에서 할 일 처리 (예: 출력, 목표 도달 확인 등)
for next_node in graph[curr]: # 연결된 다음 노드들 확인
if not visited[next_node]:
visited[next_node] = True
queue.append(next_node)
2. DFS 템플릿 (모든 경로 탐색, 덩어리 개수)
DFS는 **재귀(Recursion)**를 사용하며, "한 놈만 끝까지 팬다"는 느낌으로 구현합니다.
Python
import sys
# 재귀 깊이 제한 해제 (DFS 필수)
sys.setrecursionlimit(10**6)
def dfs(curr, graph, visited):
visited[curr] = True
# 현재 노드(curr)에서 할 일 처리
for next_node in graph[curr]:
if not visited[next_node]:
dfs(next_node, graph, visited)
3. 2차원 격자(미로, 지도) 탐색용 만능 도구
실제 시험에서는 '컴퓨터 연결'보다 '지도에서 상하좌우 이동' 문제가 더 많이 나옵니다. 이때는 아래의 방향 벡터를 함께 외우세요.
Python
# 상, 하, 좌, 우 이동을 위한 좌표 설정
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def search(x, y):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 1. 지도를 벗어나지 않았는지 확인
# 2. 방문하지 않았거나 갈 수 있는 길인지 확인
if 0 <= nx < R and 0 <= ny < C:
# 이동 로직 작성
pass
💡 외우기 위한 핵심 요약
- 데이터 저장: 인접 리스트(graph = [[] for _ in range(n)]) 형식을 가장 추천합니다.
- 방문 체크: visited 배열은 중복 방문을 막아 무한 루프와 시간 초과를 방지합니다.
- 선택 기준:
- BFS: 최단 거리, 가중치가 없는 그래프 탐색.
- DFS: 모든 경우의 수를 따져야 할 때, 재귀가 직관적일 때.
백준 1926번 '그림' 문제는 제가 앞서 설명해 드린 **'2차원 격자 탐색용 만능 도구'**와 **'BFS 템플릿'**을 결합하여 풀기에 가장 완벽한 문제입니다.
이 문제의 핵심은:
- 덩어리의 개수 (그림의 개수)를 센다.
- 덩어리 중 가장 큰 넓이 (BFS가 몇 번 돌아가는지)를 찾는다.
🐍 백준 1926번 BFS 풀이 (만능 템플릿 응용)
Python
import sys
from collections import deque
# 1. 입력 받기 (빠른 입력을 위해 sys.stdin.readline 사용)
input = sys.stdin.readline
n, m = map(int, input().split()) # 세로 n, 가로 m
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
# 2. 방향 벡터 (상, 하, 좌, 우) - 만능 도구!
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque([(x, y)])
visited[x][y] = True
area = 1 # 그림의 넓이 (시작점 포함이므로 1부터 시작)
while queue:
cx, cy = queue.popleft()
for i in range(4):
nx, ny = cx + dx[i], cy + dy[i]
# 템플릿 규칙: 1.지도 안인가? 2.방문 안했나? 3.그림(1)인가?
if 0 <= nx < n and 0 <= ny < m:
if not visited[nx][ny] and graph[nx][ny] == 1:
visited[nx][ny] = True
queue.append((nx, ny))
area += 1 # 큐에 넣을 때마다 넓이 1 증가
return area
# 3. 전체 순회하며 새로운 그림 찾기
count = 0 # 그림의 개수
max_area = 0 # 가장 큰 넓이
for i in range(n):
for j in range(m):
# 아직 방문 안 했고 그림(1)인 곳을 발견하면 BFS 시작!
if graph[i][j] == 1 and not visited[i][j]:
count += 1
current_area = bfs(i, j)
max_area = max(max_area, current_area)
# 4. 결과 출력
print(count)
print(max_area)
💡 템플릿 적용 포인트 레슨
- dx, dy 활용: 2차원 배열 탐색에서 상하좌우를 체크할 때 if문을 4번 쓰는 대신 for i in range(4)로 깔끔하게 처리했습니다.
- area 계산: BFS는 한 덩어리를 완전히 훑을 때까지 멈추지 않습니다. 따라서 queue.append가 일어나는 횟수가 곧 그 그림의 넓이가 됩니다.
- 이중 for문 순회: n x m 전체를 돌면서 **"방문하지 않은 그림(1)"**을 만날 때마다 새로운 BFS를 호출합니다. 이것이 바로 '네트워크' 문제에서 visited를 체크하며 네트워크 개수를 늘렸던 것과 똑같은 로직입니다.
⚠️ 주의할 점
- 그림이 하나도 없는 경우 max_area는 0이 나와야 합니다. 위 코드는 max_area를 0으로 초기화해두었으므로 자연스럽게 해결됩니다.
이 코드를 백준에 제출해보시면 바로 통과될 거예요! 이 구조가 아까 '네트워크' 문제 풀이와 얼마나 비슷한지 비교해보시면 "아, 이게 만능 템플릿이구나!" 하고 감이 오실 겁니다.