[Gold III] 최소비용 구하기 2 - 11779
성능 요약
메모리: 122568 KB, 시간: 256 ms
분류
데이크스트라, 그래프 이론, 최단 경로
제출 일자
2025년 1월 14일 04:30:49
문제 설명
n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.
입력
첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.
출력
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.
셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다. 경로가 여러가지인 경우 아무거나 하나 출력한다.
풀이
import heapq
INF = float('inf') # 무한대 값 설정 (거리 초기화용)
def deijkstra(start):
distances[start] = 0 # 시작 노드의 거리를 0으로 초기화
q = []
heapq.heappush(q, (start, 0)) # 우선순위 큐에 시작 노드 추가
while q:
node, weight = heapq.heappop(q) # 현재 노드와 가중치 가져오기
# 현재 저장된 거리보다 크면 무시 (이미 더 짧은 경로를 처리함)
if weight > distances[node]:
continue
# 현재 노드와 연결된 모든 인접 노드 확인
for nxt_node, nxt_weight in edges[node]:
# 새로운 경로가 기존 경로보다 짧으면 업데이트
if distances[nxt_node] > nxt_weight + weight:
distances[nxt_node] = nxt_weight + weight # 거리 갱신
prev_node[nxt_node] = node # 경로 추적을 위한 이전 노드 저장
heapq.heappush(q, (nxt_node, distances[nxt_node])) # 우선순위 큐에 추가
n = int(input()) # 도시 개수 (노드 수)
m = int(input()) # 버스 개수 (간선 수)
# 그래프 초기화 (1번 노드부터 n번 노드까지 사용)
edges = [[] for _ in range(n + 1)]
for _ in range(m):
s, e, w = map(int, input().split()) # 시작 노드, 끝 노드, 가중치 입력
edges[s].append((e, w)) # 방향 그래프 간선 추가
start, end = map(int, input().split()) # 시작 노드와 도착 노드 입력
distances = [INF] * (n + 1) # 모든 노드의 최단 거리를 무한대로 초기화
prev_node = [0] * (n + 1) # 경로 추적을 위한 이전 노드 정보 초기화
deijkstra(start) # 다익스트라 알고리즘 실행
print(distances[end]) # 도착 노드까지의 최단 거리 출력
# 최단 경로 역추적
path = [end]
now = end
while now != start:
now = prev_node[now] # 이전 노드를 따라가며 경로 추적
path.append(now)
path.reverse() # 경로를 역순으로 정렬 (출발 노드부터 표시되도록)
print(len(path)) # 경로에 포함된 노드 수 출력
print(*path) # 경로 출력
1. 초기 설정
- INF = float('inf')
- 초기 거리를 무한대 값으로 설정하기 위한 상수입니다. 그래프 상에서 도달할 수 없는 노드와 구분하기 위해 사용됩니다.
- n, m
- n: 노드(도시)의 개수.
- m: 간선(버스 노선)의 개수.
- edges
- 노드 간 연결 정보를 저장하는 인접 리스트입니다.
- edges[i]는 노드 i에서 출발하는 모든 간선의 리스트를 나타내며, 각 항목은 (도착 노드, 가중치) 형태입니다.
- distances
- 각 노드까지의 최단 거리를 저장하는 리스트입니다. 초기값은 모두 INF로 설정되며, 시작 노드의 거리는 0으로 갱신됩니다.
- prev_node
- 최단 경로를 구성하기 위해 각 노드의 이전 노드를 저장하는 리스트입니다. 추적을 위해 초기값은 모두 0으로 설정됩니다.
2. 다익스트라 알고리즘
- def dijkstra(start):
- 특정 시작 노드에서 다른 모든 노드까지의 최단 거리를 계산하는 함수입니다.
- 이 알고리즘은 우선순위 큐(heapq)를 사용하여 현재까지 계산된 최단 거리 중 가장 작은 값을 가진 노드를 탐색합니다.
- 작동 방식
- 시작 노드 초기화
- distances[start]를 0으로 설정하여 시작 노드까지의 거리를 초기화합니다.
- 우선순위 큐에 (시작 노드, 거리 0)을 추가합니다.
- 노드 처리
- 큐에서 가장 작은 가중치(거리)를 가진 노드를 꺼내옵니다.
- 이미 처리한 거리보다 크면 무시합니다. 이는 이미 더 짧은 경로를 탐색했음을 의미합니다.
- 인접 노드 갱신
- 현재 노드와 연결된 모든 인접 노드를 확인합니다.
- 새로운 경로(현재 노드까지의 거리 + 간선 가중치)가 기존 경로보다 짧으면:
- distances 리스트를 갱신합니다.
- prev_node 리스트에 현재 노드를 저장하여 경로 추적이 가능하도록 합니다.
- 갱신된 거리와 노드를 우선순위 큐에 추가합니다.
- 시작 노드 초기화
3. 입력 처리
- 그래프 정보 입력
- m개의 간선 정보를 입력받아 인접 리스트 edges를 구성합니다.
- 각 입력은 s, e, w 형식으로, 시작 노드 s에서 도착 노드 e로 가는 가중치 w를 나타냅니다.
- 시작 노드와 도착 노드 입력
- start: 경로 계산을 시작할 노드.
- end: 최단 거리를 계산할 대상 노드.
4. 최단 거리 및 경로 출력
- 최단 거리
- distances[end]를 출력하여 시작 노드에서 도착 노드까지의 최단 거리를 표시합니다.
- 최단 경로 추적
- prev_node 리스트를 사용하여 도착 노드부터 시작 노드까지의 경로를 역순으로 추적합니다.
- path 리스트에 경로를 저장하고, 이를 역순으로 뒤집어 시작 노드부터 표시되도록 정렬합니다.
5. 최종 출력
- 최단 거리: 시작 노드에서 도착 노드까지의 거리.
- 경로 노드 수: 최단 경로에 포함된 노드의 수.
- 경로: 최단 경로에 포함된 노드들.
이번엔 다익스트라 구현 까지는 잘 하였으나, 다익스트라 알고리즘 작동 방식 에서 2번째 노드 처리 부분에서 이미 처리한 노드보다 크면 무시한다는 조건을 넣지 못하여 계속해서 시간 초과가 발생하였다. 그리고 최단 거리를 다녀가는 마을 루트를 어떻게 작성할지에 대해서도 문제가 풀리지 않아 다른 분의 코드를 참고 하였다.
확실히 골드 문제는 전의 브론즈 실버 문제들과는 난이도 면에서 어렵다는 생각이 들었다.