"

수업 목표

본 수업은 관계를 표현하는 가장 강력한 추상 도구인 그래프(Graph)의 개념과 탐색 기법, 그리고 다양한 최단 경로 알고리즘을 학습하는 것을 목표로 합니다. - 그래프의 두 가지 표현 방식(인접 행렬 및 인접 리스트)의 장단점을 파악하고 상황에 맞게 구현합니다. - 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 상태 탐색 순서 차이 및 최단 거리 도달 원리를 이해합니다. - 가중치 그래프에서의 최단 경로 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜)의 동작 논리를 습득합니다. - 최소 신장 트리(MST)를 구하기 위한 크루스칼(Kruskal) 알고리즘의 원리를 파악합니다.

학습 동기부여

그래프는 단순 도로 네트워크뿐만 아니라 소셜 네트워크, 컴파일러 의존성 검사, 네트워크 라우팅 등 현실 세계의 거의 모든 관계적 데이터 구조를 모델링하는 핵심 이론입니다. 특히 시간 제한이 빡빡한 PS 환경에서 정점과 간선의 수($V, E$)에 맞춰 최적의 자료구조와 알고리즘(예: 우선순위 큐 기반 다익스트라)을 선택해 연산량을 최소화하는 훈련은 경쟁 프로그래밍과 고성능 서비스 백엔드 개발 모두를 관통하는 핵심 역량입니다.

도입 스토리

스마트폰 지도 앱에서 내 위치부터 목적지까지의 가장 빠른 대중교통 경로를 실시간으로 탐색해 주는 과정을 상상해 봅시다. 수백만 개의 버스 정류장과 지하철역이 얽혀있는 거대한 네트워크 속에서, 단 0.1초 만에 최적의 경로를 찾아내기 위해 내부적으로는 그래프 최단 경로 탐색 알고리즘이 돌고 있습니다. 정렬 상태가 아닌 복잡한 관계망 속에서 질서를 찾고 최단 거리를 파고드는 강력한 그래프 탐색 프로세스를 이론과 함께 파헤쳐 봅시다.

1. 그래프 표현과 탐색 (DFS / BFS)

파이썬에서 그래프를 구현할 때는 일반적으로 인접 리스트(Adjacency List)를 사용하여 공간과 시간 효율을 극대화합니다. - DFS(깊이 우선 탐색)는 재귀 함수나 스택을 사용하여 한 경로를 끝까지 탐색하고 돌아오는 방식입니다. 파이썬에서는 재귀 깊이 제한을 늘려야 런타임 에러를 방지할 수 있습니다. - BFS(너비 우선 탐색)는 큐(Queue)를 사용하여 가까운 노드부터 탐색하는 방식이며, 가중치가 없는 그래프에서 최단 거리를 보장합니다.

# 8038번: 방 개수 세기 — BFS 컴포넌트 탐색
import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
grid = [list(input().strip()) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

def bfs(r, c):
    q = deque([(r, c)])
    visited[r][c] = True
    while q:
        curr_r, curr_c = q.popleft()
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = curr_r + dr, curr_c + dc
            if 0 <= nr < n and 0 <= nc < m:
                if grid[nr][nc] == '.' and not visited[nr][nc]:
                    visited[nr][nc] = True
                    q.append((nr, nc))

rooms = 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == '.' and not visited[i][j]:
            bfs(i, j)
            rooms += 1

print(rooms)

2. 최단 경로 (Dijkstra / Bellman-Ford)

- 다익스트라(Dijkstra) 알고리즘은 음의 가중치가 없는 그래프에서 단일 시작점 최단 거리를 $O(E \log V)$에 찾습니다. 우선순위 큐(heapq)를 이용해 구현합니다. - 벨만-포드(Bellman-Ford) 알고리즘은 음의 가중치나 음수 사이클이 존재하는 그래프에서 사용되며, $O(VE)$ 시간 복잡도를 가집니다.

# 8041번: 가장 단거리 경로 I — 다익스트라 최단 경로
import heapq
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    adj[u].append((v, w))

dist = [float('inf')] * (n + 1)
dist[1] = 0
pq = [(0, 1)]  # (거리, 노드)

while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]:
        continue
    for v, w in adj[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(pq, (dist[v], v))

print(*(dist[1:]))

3. 최소 신장 트리 (MST) — Kruskal / Union-Find

최소 신장 트리는 모든 정점을 최소 비용으로 사이클 없이 연결한 트리입니다. 크루스칼(Kruskal) 알고리즘은 간선들을 비용 기준으로 오름차순 정렬한 뒤, 서로 분리된 집합을 합치는 Union-Find 구조를 활용하여 간선을 선택합니다.

# 8042번: 도로 보수 — 크루스칼 MST 구현
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
edges = []
for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((w, u, v))

edges.sort()
parent = list(range(n + 1))

def find(i):
    if parent[i] == i:
        return i
    parent[i] = find(parent[i])
    return parent[i]

def union(i, j):
    root_i = find(i)
    root_j = find(j)
    if root_i != root_j:
        parent[root_i] = root_j
        return True
    return False

mst_weight = 0
edges_count = 0
possible = True

for w, u, v in edges:
    if union(u, v):
        mst_weight += w
        edges_count += 1
        if edges_count == n - 1:
            break

if edges_count == n - 1 or n == 1:
    print(mst_weight)
else:
    print("IMPOSSIBLE")

4. 가중치가 0 또는 1인 특수 최단 경로 — 0-1 BFS

간선의 가중치가 0과 1 두 가지만 존재할 때, 우선순위 큐 대신 양방향 큐(Deque)를 사용하여 다익스트라를 최적화할 수 있습니다. 가중치가 0인 이동은 큐의 앞에(appendleft), 1인 이동은 큐의 뒤에(append) 넣어 큐의 정렬 상태를 $O(1)$로 보장하며 탐색합니다.

# 8043번: 0-1 최단 경로 — 0-1 BFS 구현
from collections import deque
import sys
input = sys.stdin.readline

def solve():
    r, c = map(int, input().split())
    grid = [list(input().strip()) for _ in range(r)]
    dist = [[float('inf')] * c for _ in range(r)]
    dist[0][0] = 0
    q = deque([(0, 0)])
    
    while q:
        curr_r, curr_c = q.popleft()
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = curr_r + dr, curr_c + dc
            if 0 <= nr < r and 0 <= nc < c:
                # 같은 알파벳이면 가중치 0, 다르면 1
                cost = 0 if grid[curr_r][curr_c] == grid[nr][nc] else 1
                if dist[curr_r][curr_c] + cost < dist[nr][nc]:
                    dist[nr][nc] = dist[curr_r][curr_c] + cost
                    if cost == 0:
                        q.appendleft((nr, nc))
                    else:
                        q.append((nr, nc))
                        
    print(dist[r-1][c-1])

자주 하는 실수 & 오류 예방

- 재귀 깊이 한도 초과: 파이썬의 기본 재귀 깊이 제한은 1000입니다. 트리나 그래프의 깊이가 깊어질 경우 DFS를 실행하면 Recursionerror가 발생하므로 반드시 sys.setrecursionlimit(10**6)을 선언하십시오. - BFS 방문 체크 시점: BFS를 돌릴 때 큐에서 꺼낸 다음 방문 체크를 하면, 동일한 노드가 큐에 대기하는 동안 여러 번 다시 추가되어 탐색 큐가 폭발하고 시간/메모리 초과를 냅니다. 항상 큐에 넣기 직전에 방문 처리를 완료해 주십시오. - 우선순위 큐 삽입 튜플 배치: 파이썬 heapq는 튜플의 첫 번째 값을 최우선 키로 인식하여 비교합니다. 다익스트라 가중치 거리를 기준으로 꺼내고 싶다면 반드시 (거리, 노드) 구조로 우선순위 키인 거리를 맨 앞에 두십시오.

핵심 정리

그래프 유형	기본 탐색 방식 및 특징	소요 시간 복잡도	적합한 적용 조건
기본 탐색	DFS (재귀 기반) / BFS (Queue 기반)	$O(V + E)$	모든 노드 탐색 및 단순 컴포넌트 분할
0-1 가중치	0-1 BFS (Deque 활용)	$O(V + E)$	간선 비용이 오직 0 또는 1로만 제한된 경우
양의 가중치	Dijkstra (heapq 활용)	$O(E \log V)$	음의 가중치가 없는 단일 시작점 최단 경로
음의 가중치	Bellman-Ford (모든 간선 완화)	$O(VE)$	음의 가중치 포함 및 음수 사이클 존재 판별
모든 쌍 경로	Floyd-Warshall (3중 루프 DP)	$O(V^3)$	정점 개수 V가 500 이하인 소형 그래프 전체 탐색
최소 신장 트리	Kruskal (정렬 + Union-Find)	$O(E \log E)$	네트워크의 모든 노드를 최소 총합 비용으로 연결

실습 문제

문제 번호	문제 제목	출처	난이도	핵심 알고리즘
8038	방 개수 세기	CSES	보통	BFS / DFS 컴포넌트 탐색
8039	미로 탐색	CSES	보통	BFS 최단 경로 및 경로 역추적
8040	도로 건설	CSES	보통	BFS / DFS / Union-Find 연결 컴포넌트
8041	가장 단거리 경로 I	CSES	보통	우선순위 큐 다익스트라 알고리즘
8042	도로 보수	CSES	보통	크루스칼 알고리즘 & 최소 신장 트리(MST)
8043	0-1 최단 경로	SPOJ	보통	양방향 큐(Deque) 0-1 BFS 최적화
8044	통화 환전	POJ	보통	벨만-포드 양수 사이클 판정