1753

[c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 )

다익스트라 다익스트라는 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 단일 시작점 알고리즘에 속하여 시작점을 기준으로 각 노드까지의 최단 거리를 알 수 있다. 이때 시간 복잡도를 줄이기 위해 우선순위 큐를 활용하면 좋다. 음수 간선이 없을때 사용 (음수가 있으면 벨만-포드나 플로이드를 사용하는게 좋다) 우선순위 큐를 활용 단일 시작점 알고리즘 다익스트라 알고리즘은 BFS처럼 동작한다. 시작점에서부터 BFS탐색을 진행한다. 단, 우선순위 큐에서 노드를 뽑을때는 간선의 가중치가 가장 낮은 노드를 뽑는다.(우선순위 큐에 {-가중치,노드} 형태로 넣으면 된다.) 해당 노드와 접한 노드를 뽑아서 dp에 최단경로를 메모이제이션한다. 이후 최단경로 가중치를 노드와 함께 큐에 넣고 루프를 돌며 반복한다. 문..