-
1916. [Python]최소비용 구하기Python_알고리즘/Gold V 2024. 3. 5. 01:02
1. 문제
https://www.acmicpc.net/problem/1916
2. 접근 방법
- 시간 제한: 0.5초
- 메모리 제한: 128MB
- 다익스트라
- 우선순위 큐
3. 파이썬 코드
import sys import heapq input = sys.stdin.readline N = int(input()) M = int(input()) matrix = [ [] for _ in range(N+1)] # 다익스트라 거리 distance = [10**9] * (N+1) for _ in range(M): S, E, W = map(int,input().split()) matrix[S].append((W,E)) # 시작점과 끝점 start, target = map(int,input().split()) # 다익스트라 알고리즘 def dijkstra(start): # 시작하는 값의 코스트는 0 이고 시작점이 주어지므로 queue 초기값 선언 queue = [(0,start)] # 초기 거리 0 으로 설정 distance[start] = 0 # queue 값이 빌때까지 while queue: # 거리, 노드 순으로 저장했기 때문에 출력 dist, now = heapq.heappop(queue) # 노드의 거리가 현재 가지고있는 값보다 작은경우 다음 반복문 if distance[now] < dist: continue # 노드와 연결된 노드들 탐색 for next in matrix[now]: # cost 라는 변수에 현재 노드의 가중치 + 연결된 노드의 가중치 값 계산 cost = dist + next[0] # 만약 연결된 노드의 가중치보다 cost 값이 작은 경우 값 갱신 후 가중치, 노드번호 추가 if distance[next[1]] > cost: distance[next[1]] = cost heapq.heappush(queue,(cost, next[1])) dijkstra(start) print(distance[target])
4. 문제를 풀고난 후 생각
- 다익스트라 알고리즘에 대해서 공부를 하고 있는 요즘 비슷한 유형의 문제들을 풀고있다.
- 다익스트라 알고리즘의 경우 임의의 노드에서 각 모든 노드까지 최단거리를 구할 수 있는 알고리즘이다.
- 위 문제는 다익스트라 알고리즘의 기초적인 문제로 다익스트라 알고리즘을 구현할 수 있는지를 물어보는 문제였다.
- 우선순위 큐를 사용한 이유는 (가중치, 노드) 순으로 넣어서 가중치 값이 작은 값부터 노드를 확인해가며 가중치 값이 큰경우 불필요한 연산을 줄이기 위해서 우선순위 큐를 사용하여 시간적인 부분을 해결했다.
5. 문제를 푸는데 도움이 되는 지식
- 다익스트라
- 우선순위 큐
'Python_알고리즘 > Gold V' 카테고리의 다른 글
7682. [Python]틱택토 (0) 2024.04.17 1456. [Python]거의 소수 (0) 2024.04.14 2023. [Python] 신기한 소수 (1) 2024.02.25 9205. [Python] 맥주 마시면서 걸어가기 (0) 2024.02.18 1593. [Python]문자 해독 (1) 2023.12.28