-
1753. [Python]최단경로Python_알고리즘/Gold IV 2024. 3. 3. 23:59
1. 문제
https://www.acmicpc.net/problem/1753
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 256MB
- 다익스트라
3. 파이썬 코드
import sys import heapq input = sys.stdin.readline # 시작점을 기준으로 다익스트라 시작 def BFS(init): # queue 리스트 생성 queue = [] # 우선순위 큐 생성 heapq.heappush(queue,(0,init)) distance[init] = 0 # queue 가 빌때까지 실행 while queue: # queue에 거리, 노드 순으로 저장 dist, now = heapq.heappop(queue) # 노드의 거리가 현재 거리보다 작은경우 무시 if distance[now]<dist: continue # 외의 경우 현재 노드와 연결된 노드를 반복 for i in matrix[now]: # 현재 거리 + 연결된 노드의 가중치 증가 cost = dist + i[0] # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우 if cost < distance[i[1]]: # 거리 값을 최소값으로 갱신 distance[i[1]]=cost # queue 리스트에 가중치, 노드 순으로 저장 heapq.heappush(queue,(cost,i[1])) V, E = map(int,input().split()) distance = [10**9] * (V+1) start = int(input()) matrix = [[] for _ in range(V+1)] for _ in range(E): S, E, W = map(int,input().split()) matrix[S].append((W, E)) BFS(start) for i in range(1,V+1): if distance[i] == 10**9: print("INF") else: print(distance[i])
4. 문제를 풀고난 후 생각
- 다익스트라 알고리즘에 대해서 공부가 좀 더 필요한 것 같다.
- 기존의 BFS와 비슷한 방식으로 접근을 했을때는 시간초과가 발생했으며 우선순위 큐를 통해서 비용을 먼저 저장하여 시작 노드를 기준으로 비용이 낮은순으로 queue 값을 갱신해 나가는 방식으로 문제를 풀었다.
- 이 문제의 경우 비용과 노드의 위치를 바꿔서 저장하는 경우 노드의 위치가 먼저 우선순위 비교가 되기 때문에 불필요한 값이 추가될 수 있어서 그러한 연산의 가지치기를 cost 값을 우선으로 두면서 시간초과를 안나오게 했어야 했다.
개인적으로 다익스트라 알고리즘에 대해서 한번 정리를 진행한 후 문제를 풀어봐야 할 것 같다.
5. 문제를 푸는데 도움이 되는 지식
- 다익스트라 알고리즘
- 우선순위 큐
'Python_알고리즘 > Gold IV' 카테고리의 다른 글
1253. [Python] 좋다 (1) 2024.03.13 1261. [Python]알고스팟 (1) 2024.03.06 17425. [Python]약수의 합 (1) 2023.10.09 9019. [Python]DSLR (1) 2023.10.08 10942. [Python]팰린드롬? (1) 2023.10.07