다익스트라알고리즘 (1) 썸네일형 리스트형 [백준/알고리즘] 1916번 최소비용 구하기 (골드 5) BOJ 1916번 N개의 도시가 있고, 도시 사이를 이동하는 버스 M개가 있다. 도시 A에서 도시 B로 가는 버스 비용을 최소화 하려고 한다. 최소 비용을 출력하시오. 풀이 알고리즘 : 다익스트라 알고리즘 한 정점에서 다른 정점으로 이동하는 최소 거리를 구하는 문제입니다.도시 A에서 다른 모든 정점으로의 최소 거리를 구하기 위해 다익스트라 알고리즘을 이용하여 구현하였습니다. 모든 도시를 이중 for문으로 탐색하여 구하는 방법이 있고,우선순위 큐를 이용하여 구하는 방법이 있는데, 후자가 보통 빠르기에 우선순위 큐를 이용하여 구현하겠습니다. 우선순위큐에 를 입력하였고, 거리가 가까운 정점을 우선순위로 탐색하고,해당 정점에서 또 확인하지 않고 연결되어 있는 정점으로의 최소 거리를 갱신하여 PQ에 다시 입력하는.. 이전 1 다음
