알고리즘 문제풀이[Algorithm]
[백준] 1916번 최소비용 구하기(다익스트라 알고리즘)(Python - 파이썬)
백준 1916번 문제입니다. (solved.ac)기준 골드 5 문제입니다. 문제 접근 [백준] 1753번 최단경로(다익스트라 알고리즘)(Python) 위의 문제와 마찬가지로 다익스트라 알고리즘으로 간단하게 최소 비용을 구할 수 있는 문제입니다. 위의 문제와 다른 점은 1916번 문제는 노드의 수(N)가 최대 1,000개이기 때문에 이 문제는 우선순위 큐를 사용하지 않는, 시간복잡도가 O(N^2)인 간단한 다익스트라 알고리즘은로도 문제를 해결할 수 있습니다. 간단한 다익스트라 알고리즘은 1. 출발 노드(start)를 설정 2. 최단 거리 테이블(distance)을 int(1e9)로 설정(노드 수 만큼) 3. 방문하지 않은 노드(visited = False) 중 최단 거리(distance)가 가장 짧은 노드..
2022. 2. 23. 16:20
최근댓글