학습 목표: 그래프 표현 (인접 리스트/행렬) · DFS/BFS 기본 구현 · 연결 요소, 최단 경로 문제 · 격자(Grid) 탐색 패턴
1️⃣ 그래프 표현 방법
그래프란?
노드(정점, Node) 와 간선(Edge) 으로 이루어진 자료구조. 현실 세계의 지도, 소셜 네트워크, 도로망 등을 표현할 때 쓴다.
노드: 장소, 사람, 상태
간선: 연결, 관계, 이동 가능 여부
인접 행렬 (Adjacency Matrix)
2차원 배열로 표현. graph[i][j] = 1이면 i → j 연결.
# 노드 4개, 간선: 1-2, 1-3, 2-4, 3-4
n = 4
graph = [[0] * (n+1) for _ in range(n+1)]
edges = [(1,2), (1,3), (2,4), (3,4)]
for u, v in edges:
graph[u][v] = 1
graph[v][u] = 1 # 무방향 그래프면 양쪽 다
# graph[1][2] = 1, graph[1][3] = 1, ...
✅ 장점: 연결 여부를 O(1)로 확인
❌ 단점: 노드가 많으면 메모리 낭비 (N² 공간)
인접 리스트 (Adjacency List)
각 노드가 연결된 노드 목록만 저장. 실전에서 거의 이걸 쓴다!
from collections import defaultdict
graph = defaultdict(list)
edges = [(1,2), (1,3), (2,4), (3,4)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # 무방향 그래프
# graph = {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3]}
장점: 메모리 효율적 (실제 간선 수만큼만)
단점: 연결 여부 확인이 O(degree)
degree = 해당 노드에 연결된 간선의 수 예를 들어 노드 1이 2, 3, 4에 연결돼 있으면 degree = 3.
언제 뭘 써?
노드 수가 적고 (N ≤ 1000), 간선이 많으면 → 인접 행렬
노드 수가 많고, 간선이 적으면 → 인접 리스트 (대부분의 경우)
격자(Grid) 형태의 문제 → 2차원 배열 그대로 사용
2️⃣ DFS (깊이 우선 탐색, Depth First Search)
개념
한 방향으로 끝까지 파고들다가, 더 갈 곳이 없으면 되돌아와서 다른 방향 탐색.
🌲 비유: 미로에서 한 방향을 선택하고 막힐 때까지 직진, 막히면 갈림길로 되돌아가는 것!
탐색 순서 예시:
1
/ \\
2 3
/ \\
4 5
DFS: 1 → 2 → 4 → 5 → 3 (깊이 우선)
BFS: 1 → 2 → 3 → 4 → 5 (너비 우선)
DFS 구현 - 재귀 방식
def dfs(graph, node, visited):
visited.add(node)
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
graph = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}
dfs(graph, 1, set())
# 출력: 1 2 4 5 3
DFS 구현 - 스택 방식 (재귀 한도 초과 시)
def dfs_stack(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop() # 스택에서 꺼내기
if node not in visited:
visited.add(node)
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
graph = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}
dfs_stack(graph, 1)
⚠️ 파이썬 재귀 한도는 기본 1000!
노드가 많으면sys.setrecursionlimit(10**6)추가하거나 스택 방식으로 구현한다.
3️⃣ BFS (너비 우선 탐색, Breadth First Search)
개념
시작점에서 가까운 노드부터 차례대로 탐색. 거리(레벨) 순으로 방문.
🌊 비유: 돌을 물에 던지면 파문이 동심원으로 퍼져나가는 것처럼, 시작점에서 거리 1, 2, 3… 순으로 탐색!
핵심: deque + visited 세트
시작 노드를 큐에 넣고 → 꺼내면서 이웃 탐색 → 방문 안 한 이웃을 큐에 추가
BFS 구현
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft() # 큐에서 꺼내기
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
graph = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}
bfs(graph, 1)
# 출력: 1 2 3 4 5
BFS가 최단 경로를 보장하는 이유
def bfs_shortest(graph, start, end):
visited = {start: 0} # {노드: 거리}
queue = deque([start])
while queue:
node = queue.popleft()
if node == end:
return visited[end]
for neighbor in graph[node]:
if neighbor not in visited:
visited[neighbor] = visited[node] + 1
queue.append(neighbor)
return -1 # 도달 불가
# BFS는 거리 순으로 탐색하기 때문에
# 처음 목적지에 도달했을 때가 반드시 최단 거리!
💡 핵심: BFS는 레벨(거리) 순서로 탐색하기 때문에,
가중치 없는 그래프에서 최단 경로 = BFS 가 공식임.
4️⃣ DFS vs BFS - 언제 뭘 써야 해?
📌 DFS를 써야 할 때
경로 자체를 탐색하거나, 모든 경우를 탐색해야 할 때
- 연결 요소(Connected Component) 개수 세기
- 사이클 감지
- 백트래킹 문제 (경로에 특정 조건이 있을 때)
- 그래프가 크고 목표가 깊은 곳에 있을 때
모든 정점 방문이 목표 → DFS
경로의 특징 저장 필요 → DFS
📌 BFS를 써야 할 때
시작점에서 최단 거리/최소 횟수를 구해야 할 때
- 최단 경로 문제 (가중치 없는 그래프)
- 레벨 탐색 (몇 단계 만에 도달 가능한지)
- 격자에서 최소 이동 횟수 구하기
최단 거리 필요 → BFS
레벨 단위 탐색 필요 → BFS
"몇 번 만에 가능?" → BFS
✅ 한 줄 요약
모든 경로 탐색, 연결 확인 → DFS
최단 거리, 최소 횟수 → BFS
모르겠으면 → 일단 BFS 먼저 고려 (최단 경로 보장하니까)
5️⃣ 연결 요소 (Connected Components)
개념
그래프에서 서로 이어진 노드 그룹의 수를 세는 것. 섬 개수 세기, 단지 개수 세기 등에 활용.
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 neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
for node in range(1, n+1):
if node not in visited:
dfs(node) # 새로운 연결 요소 발견!
count += 1
return count
# 노드 5개, 간선: (1,2), (3,4)
print(count_components(5, [(1,2),(3,4)])) # 3 (1-2 묶음, 3-4 묶음, 5 혼자)
6️⃣ 격자(Grid) 탐색 패턴
개념
2차원 배열(지도, 미로)을 그래프처럼 탐색하는 패턴. 코딩테스트에서 가장 자주 나오는 형태!
# 상하좌우 이동 방향 벡터 (격자 탐색의 국룰)
dr = [-1, 1, 0, 0] # 행 변화
dc = [0, 0, -1, 1] # 열 변화
# 범위 체크 (이것도 국룰)
def in_bound(r, c, rows, cols):
return 0 <= r < rows and 0 <= c < cols
격자 DFS - 연결된 영역 크기 구하기
def dfs_grid(grid, r, c, visited):
rows, cols = len(grid), len(grid[0])
visited[r][c] = True
size = 1
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for i in range(4):
nr, nc = r + dr[i], c + dc[i]
if 0 <= nr < rows and 0 <= nc < cols:
if not visited[nr][nc] and grid[nr][nc] == 1:
size += dfs_grid(grid, nr, nc, visited)
return size
grid = [
[1, 1, 0, 0],
[1, 0, 0, 1],
[0, 0, 1, 1],
]
visited = [[False]*4 for _ in range(3)]
print(dfs_grid(grid, 0, 0, visited)) # 3 (연결된 1의 개수)
격자 BFS - 최단 거리 구하기
from collections import deque
def bfs_grid(grid, start_r, start_c, end_r, end_c):
rows, cols = len(grid), len(grid[0])
visited = [[False]*cols for _ in range(rows)]
queue = deque([(start_r, start_c, 0)]) # (행, 열, 거리)
visited[start_r][start_c] = True
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
while queue:
r, c, dist = queue.popleft()
if r == end_r and c == end_c:
return dist
for i in range(4):
nr, nc = r + dr[i], c + dc[i]
if 0 <= nr < rows and 0 <= nc < cols:
if not visited[nr][nc] and grid[nr][nc] != 1: # 벽이 아니면
visited[nr][nc] = True
queue.append((nr, nc, dist + 1))
return -1 # 도달 불가
🎯 격자 BFS 핵심 3가지:
1. visited 처리는 큐에 넣을 때 (꺼낼 때 하면 중복 방문 발생!) 2. 범위 체크 + 벽 체크를 동시에 3. 큐에 (행, 열, 거리)를 함께 저장
7️⃣ 그래프 탐색 5문제 풀이
✅ 문제 1 - DFS와 BFS 동시 구현
import sys
from collections import deque
input = sys.stdin.readline
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in sorted(graph[v]): # 번호 작은 것부터
if not visited[i]:
dfs(graph, i, visited)
def bfs(graph, start, n):
visited = [False] * (n+1)
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=' ')
for i in sorted(graph[v]):
if not visited[i]:
visited[i] = True
queue.append(i)
✅ 문제 2 - 단지 개수 세기 (격자 DFS)
def solution(grid):
n = len(grid)
visited = [[False]*n for _ in range(n)]
groups = []
def dfs(r, c):
visited[r][c] = True
count = 1
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 1:
count += dfs(nr, nc)
return count
for i in range(n):
for j in range(n):
if grid[i][j] == 1 and not visited[i][j]:
groups.append(dfs(i, j))
groups.sort()
return len(groups), groups
✅ 문제 3 - 미로 최단 경로 (격자 BFS)
from collections import deque
def shortest_path(maze):
n, m = len(maze), len(maze[0])
queue = deque([(0, 0, 1)]) # (행, 열, 거리)
visited = [[False]*m for _ in range(n)]
visited[0][0] = True
while queue:
r, c, dist = queue.popleft()
if r == n-1 and c == m-1:
return dist
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc] and maze[nr][nc] == 1:
visited[nr][nc] = True
queue.append((nr, nc, dist+1))
return -1
✅ 문제 4 - 토마토 익히기 (다중 시작점 BFS)
from collections import deque
def tomato(grid):
n, m = len(grid), len(grid[0])
queue = deque()
# 익은 토마토 전부 큐에 넣기 (다중 시작점!)
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
queue.append((i, j, 0))
max_day = 0
while queue:
r, c, day = queue.popleft()
max_day = max(max_day, day)
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 0:
grid[nr][nc] = 1
queue.append((nr, nc, day+1))
# 아직 안 익은 토마토 있으면 -1
for row in grid:
if 0 in row:
return -1
return max_day
💡 다중 시작점 BFS: 시작점이 여러 개일 때 전부 큐에 미리 넣고 시작!
토마토, 불 번지기, 바이러스 퍼짐 같은 문제에서 자주 씀.
✅ 문제 5 - 연결 요소 개수 (그래프 DFS)
import sys
sys.setrecursionlimit(10**6)
def count_connected_components(n, edges):
graph = [[] for _ in range(n+1)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * (n+1)
count = 0
def dfs(v):
visited[v] = True
for neighbor in graph[v]:
if not visited[neighbor]:
dfs(neighbor)
for i in range(1, n+1):
if not visited[i]:
dfs(i)
count += 1
return count
4주차 핵심 요약
그래프 표현
→ 인접 행렬: O(1) 탐색, 메모리 많이 씀
→ 인접 리스트: 메모리 효율적, 대부분의 경우 이걸 써
DFS
→ 재귀 or 스택으로 구현
→ 연결 요소, 백트래킹, 경로 탐색에 사용
BFS
→ deque로 구현 (list.pop(0)은 O(n)이라 느림!)
→ 가중치 없는 그래프의 최단 경로 보장
격자 탐색
→ dr, dc 방향 벡터 + 범위 체크가 국룰
→ visited는 큐에 넣을 때 처리
DFS vs BFS 선택 기준
→ 최단 거리 필요 → BFS
→ 모든 경로 탐색 → DFS
DFS vs BFS - 언제 뭘 쓰냐
연결 요소 개수 세기 어느 쪽이든 가능하지만 → DFS가 재귀로 구현이 더 직관적
미로 최단 거리 DFS로 풀면 최단 보장 안 됨 → 반드시 BFS
섬 넓이 구하기 넓이를 누적해야 하니까 → DFS (재귀로 누적하기 편함)
N단계 이내 도달 가능한 노드 수 레벨 기반 탐색 → BFS
바이러스 / 불 번지기 (다중 시작점) 시작점 여러 개를 큐에 한꺼번에 → 다중 시작점 BFS