최소 이동 거리 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 5251

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYHO7a2JoDFAVT#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

A도시에는 E개의 일방통행 도로 구간이 있으며, 각 구간이 만나는 연결지점에는 0부터 N번까지의 번호가 붙어있다. 구간의 시작과 끝의 연결 지점 번호, 구간의 길이가 주어질 때, 0번 지점에서 N번 지점까지 이동하는데 걸리는 최소한의 거리가 얼마인지 출력하는 프로그램을 만드시오. 모든 연결 지점을 거쳐가야 하는 것은 아니다. 그림은 입력인 N=2, E=3, 시작과 끝 지점, 구간 거리가 아래와 같은 경우의 예이다. 0 1 1 0 2 6 1 2 1

 

입력

첫 줄에 테스트 케이스의 개수 T가 주어지고, 테스트 케이스 별로 첫 줄에 마지막 연결지점 번호N과 도로의 개수 E가 주어진다. 다음 줄부터 E개의 줄에 걸쳐 구간 시작 s, 구간의 끝 지점 e, 구간 거리 w가 차례로 주어진다. ( 1<=T<=50, 1<=N, s, e<=1000, 1<=w<=10, 1<=E<=1000000 )

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 테스트 케이스에 대한 답을 출력한다.

예시

입력	출력
3 2 3 0 1 1 0 2 6 1 2 1 4 7 0 1 9 0 2 3 0 3 7 1 4 2 2 3 8 2 4 1 3 4 8 4 6 0 1 10 0 2 7 1 4 2 2 3 10 2 4 3 3 4 10	#1 2 #2 4 #3 10

---

2. 문제풀이

최단거리, 최소거리, 최소비용 이런게 나오면 다익스트라 알고리즘을 이용하여 풀면된다. 최소비용으로 가기위해서는 이전에도 제일 적은비용으로 가야한다는 기본적인 베이스가 깔려있다. 따라서 시작점부터 이동이 가능한 간선을 우선순위큐에 넣어두고 비용이 제일적은것을 꺼낸다음에 체크를하고 간선을 계속 추가하는 형식으로 진행한다. 큐가 비게된다면 모든 비용이 갱신되었다고 볼수있기때문에 목표점의 비용을 출력하면 된다.

---

3. 소스코드

#D4 5251 최소 이동 거리
import heapq
 
for t in range(int(input())):
    N, E = map(int, input().split())
    #0번을 기준으로  노드간의 거리를 계산
    distance =[0] + [float('inf') for _ in range(N)]
    #노드간 거리를 저장하는 변수
    node = [[] for _ in range(N+1)]
    #이미 노드를 방문했는지 체크하는 변수
    visited = [0 for _ in range(N+1)]
    #간선만큼 입력을 받아 저장
    for _ in range(E):
        a, b, c = list(map(int, input().split()))
        node[a].append((b, c))
    #약간 변형이긴한데 큐를 이용하여 시작
    #원래는 방문하지 않은것중 가장작은 노드를 찾아야함
    queue = []
    heapq.heappush(queue, (0, 0))
    #큐가 빌대까지 반복
    while queue:
        #큐에서 확인할 노드번호를 꺼냄
        d, idx = heapq.heappop(queue)
        if visited[a]:
            continue
        #방문 체크를 하고
        visited[idx] = 1
        #그 노드와 연결된 노드를 찾는다.
        for a, b in node[idx]:
            #a는 노드번호, b는 노드간 거리
            # 0번부터 노드a까지의 거리가 지금가는 경로보다
            # 비용이 크다면 갱신
            if distance[a] > d + b:
                distance[a] = d + b
                heapq.heappush(queue, (distance[a], a))
            #해당노드를 방문하지 않았다면 큐에 추가
    #노드 N번까지 거리를 보는것이므로 distance(N)을 출력
    print('#{} {}'.format(t+1, distance[N]))