학습 철학 회고
이전에 '다익스트라 완벽 해부' 포스팅에서 정리했던 특정 문제에 종속되지 않은 '순수한 다익스트라 뼈대(Template)'를 꺼내어, 실제 코딩 테스트 환경(백준 1753번)의 요구사항에 맞춰 조립해 보는 실전 훈련을 진행했습니다. 머릿속의 추상화된 논리를 실제 파이썬 코드로 번역할 때 발생하는 미세한 마찰음들을 디버깅하며 완벽한 SOP(설계 주도형 사고)를 체화했습니다.
📌 문제 요약: 1753번 최단경로
방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는, 다익스트라(Dijkstra) 알고리즘의 교과서이자 표준과도 같은 문제입니다.
- 모든 간선의 가중치는 10 이하의 자연수입니다. (음수 가중치가 없으므로 다익스트라 적용 가능)
- 정점의 개수 는 최대 20,000개, 간선의 개수 는 최대 300,000개이므로, 의 단순 탐색으로는 무조건 시간 초과가 발생합니다. 반드시 우선순위 큐(
heapq)를 활용하여 로 최적화해야 합니다.
💻 실전 조립 코드 (SOP 적용)
입력 파싱부터 알고리즘 실행, 출력까지 생명주기를 완벽하게 통제한 최종 코드입니다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한대
def dijkstra(graph, start, V) :
# 1. 메모장 초기화 및 시작점 세팅
distance = [INF] * (V+1)
distance[start] = 0
# 2. 우선순위 큐 생성 및 튜플 (비용, 노드) 삽입
pq = []
heapq.heappush(pq, (0, start))
# 3. 큐가 빌 때까지 탐색 반복
while pq:
current_cost, current_node = heapq.heappop(pq)
# [핵심 방어 로직] 큐에서 꺼낸 낡은 정보(현재 거리보다 큰 비용)는 무시
if current_cost > distance[current_node]:
continue
# 4. 인접 노드 탐색 및 지름길 갱신
for next_node, weight in graph[current_node]:
cost = current_cost + weight
# 지름길을 발견했다면 메모장 갱신 및 큐에 삽입
if distance[next_node] > cost:
distance[next_node] = cost
heapq.heappush(pq, (cost, next_node))
return distance
def solution():
V, E = map(int, input().split())
start = int(input())
# [최적화] 입력을 받는 즉시 인접 리스트(graph) 생성하여 메모리 낭비 방지
graph = [[] for _ in range(V+1)]
for _ in range(E):
u, v, w = map(int, input().split())
graph[u].append((v, w)) # (도착노드, 가중치)
distance = dijkstra(graph, start, V)
# 5. 1-based 인덱싱에 맞춘 정답 출력
for i in range(1, V+1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])
# 전역 변수 오염을 막기 위한 메인 함수 호출
if __name__ == "__main__":
solution()🚨 트러블 슈팅 및 실전 최적화 포인트
뼈대를 실전에 적용하는 과정에서 겪은 파이썬 특화 문법과 구조적 고민을 회고합니다.
1. heapq 모듈의 올바른 사용과 튜플 정렬 원리
파이썬의 힙 큐는 튜플의 '첫 번째 원소'를 기준으로 오름차순 정렬합니다. 따라서 큐에 데이터를 넣을 때 습관적으로 (노드, 비용) 순으로 넣으면 엉뚱한 탐색을 하게 됩니다. 반드시 비용(Cost)을 맨 앞에 배치한 (cost, node) 형태로 heapq.heappush에 넘겨주어 최단 거리 우선 추출을 보장해야 합니다.
2. 입력과 동시에 그래프 가공 (메모리 최적화)
모든 입력을 2차원 배열에 한 번 다 담아둔 뒤, 그걸 다시 graph[u].append((v,w))로 재가공하는 것은 시간과 공간을 2배로 낭비하는 안 좋은 습관입니다. 데이터를 읽어 들이는 for 루프 안에서 즉시 목적지인 인접 리스트에 꽂아 넣음으로써 I/O 오버헤드를 최소화했습니다.
3. 스코프(Scope) 통제를 통한 전역 변수 오염 차단
distance나 graph 같은 핵심 배열들을 무분별하게 전역으로 빼지 않고, solution()이라는 큰 틀 안에서 생성하여 dijkstra() 함수의 파라미터로 안전하게 넘겨주었습니다. 이는 향후 여러 개의 테스트 케이스가 동시에 주어지는 시뮬레이션 환경에서 이전 데이터가 섞이는 치명적인 버그를 막아주는 강력한 설계 체력(SOP)입니다.
