백준 1446 - 지름길 (Python3)

코드

import heapq
INF = float('inf')

n, d = map(int, input().split())

graph = [[] for _ in range(d+1)]

dist_table = [INF for _ in range(d+1)]

# 지름길 없이 가는 경우
# i => i+1로 가는 경우
# 가중치 1 발생
for i in range(d):
    graph[i].append((i+1, 1))

# 지름길인 경우
# 별도로 입력받음
for _ in range(n):
    a, b, c = map(int, input().split())
    
    # 가만 보면 도착 지점이 전체 길이보다 긴 경우가 있음
    # 얜 그냥 입력 제외
    if b > d:
        continue
    
    graph[a].append((b, c))
    
def dijkstra(start):
    q = []
    
    heapq.heappush(q, (0, start))
    
    dist_table[start] = 0
    
    while q:
        w, v = heapq.heappop(q)
        
        if w > dist_table[v]:
            continue
            
        for i in graph[v]:
            cost = w + i[1]
            
            if cost < dist_table[i[0]]:
                dist_table[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
    return dist_table
                
dijkstra(0)
            
print(dist_table[d])    

문제 해설

다익스트라 알고리즘 문제.

일반적으로 최단 거리 알고리즘 문제에서는 그래프의 노드에 해당하는 것이 어떤 존재인지 뚜렷하게 명시해주는 경우가 많다. 하지만 이 문제의 경우, 주어진 조건들 중, 노드로 사용해야 할 요소를 한 눈에 파악하는 것이 어려웠다. 한참을 고민한 후에 나는 주어진 고속도로를 1km 구간 별로 모두 나눠서, 나눈 각각의 구간을 노드라고 생각하기로 했다. 즉, D가 150인 경우 우린 0~150까지 총 151개의 노드를 갖게 되는 것이다.

또한 이 경우, graph를 아래와 같이 두 번 입력받아야 한다.

# 지름길 없이 가는 경우
# i => i+1로 가는 경우
# 가중치 1 발생
for i in range(d):
    graph[i].append((i+1, 1))

# 지름길인 경우
# 별도로 입력받음
for _ in range(n):
    a, b, c = map(int, input().split())
    
    # 가만 보면 도착 지점이 전체 길이보다 긴 경우가 있음
    # 얜 그냥 입력 제외
    if b > d:
        continue
    
    graph[a].append((b, c))

지름길로 가지 않는 경우엔 (i => i+1로 가는 경우) 소요 가중치가 당연히 (i+1) - i 만큼 들 것이므로 위의 for문으로 graph를 초기화 시켜주고, 그 후 주어진 지름길의 위치 정보와 가중치를 다시 한 번 입력해준다.

위의 점만 조심하면 로직 자체는 간단하므로 쉽게 해결할 수 있다.

개인 프로젝트 준비와 코로나 바이러스 감염 등, 많은 이유로 코딩 테스트 공부를 많이 소홀하게 보낸 9월 달이었다…ㅠㅠ 10월부터 다시 마음들 바로 잡고 열심히 문제를 풀어야겠다!!!