Ch 6. 동적 계획법 (Dynamic Programming)

Lesson 206. 그래프 탐색 및 최단 경로

Graph Representation, Traversals, Shortest Paths, and MST - 그래프 구조 표현 (인접 리스트 vs 인접 행렬) - 깊이/너비 우선 탐색 (DFS/BFS) 구현 구조 - 가중치 유형별 최단 경로 선택 (다익스트라, 벨만-포드) - 최소 신장 트리 (Kruskal) 설계와 0-1 BFS 최적화

수업 목표 및 핵심 역량

- 인접 리스트 방식을 활용해 공간 효율적인 그래프를 구성합니다. - BFS 탐색 시 큐에 넣는 즉시 방문 체크를 수행하여 불필요한 중복 삽입을 방지합니다. - 가중치 그래프 최단 거리 탐색을 위한 다익스트라 힙 구조를 설계합니다. - 크루스칼 알고리즘과 Union-Find를 활용하여 사이클 없는 MST를 생성합니다.

BFS 최단경로 및 경로 역추적

- BFS 탐색 과정에서 각 노드의 부모 노드와 이동 방향을 parent 배열에 동시 기록하여 역추적

# 8039번: 미로 탐색 발췌
while q:
    r, c = q.popleft()
    if (r, c) == end:
        found = True
        break
    for dir_name, (dr, dc) in dirs.items():
        nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] != '#' and not visited[nr][nc]:
            visited[nr][nc] = True
            parent[nr][nc] = (r, c, dir_name)
            q.append((nr, nc))

Dijkstra 최단 경로 구현

- 파이썬 heapq의 정렬 구조를 고려하여 (거리, 노드) 구조의 튜플로 우선순위 큐 관리

# 8041번: 가장 단거리 경로 I 발췌
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))

Kruskal 최소 신장 트리

- 간선을 가중치 순 정렬 후 Union-Find를 통해 정점이 서로 다른 컴포넌트인 경우만 간선 채택

# 8042번: 도로 보수 발췌
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

0-1 BFS 최적화 (Deque)

- 가중치가 0인 이동은 큐의 앞에(appendleft), 1인 이동은 뒤에(append) 추가해 $O(V+E)$ 최적화

# 8043번: 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))

오류 해결 및 오답 방지

- **재귀 한도 조절**: DFS 적용 시 sys.setrecursionlimit(10**6)을 반드시 명시해 에러 방지 - **방문 체크 타이밍**: BFS 탐색 시 중복 노드가 들어가지 않도록 큐에 **넣기 직전** 방문 마킹 수행 - **최소 힙 비교 순서**: 힙 큐 튜플 연산 시 반드시 (거리, 노드) 구조를 준수하여 오정렬 차단