개발새발

다익스트라 알고리즘은 그래프 이론에서 주어진 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘으로, 가중치가 있는 그래프에서 최단 경로를 찾는 문제를 해결하는 데 사용됩니다. (그래프 이론 + dp)다익스트라 알고리즘 개요다익스트라 알고리즘은 다음과 같은 단계로 동작합니다:출발 노드 선택: 시작 노드를 선택하고, 시작 노드의 최단 경로를 0으로 초기화합니다.우선순위 큐 활용: 출발 노드부터 갈 수 있는 모든 경로를 우선순위 큐(힙)에 넣습니다. 시작 노드의 최단 경로가 0이므로 시작 노드를 우선순위 큐에 넣습니다.최단 경로 갱신: 우선순위 큐에서 최소 비용의 노드를 꺼내서 해당 노드에서 갈 수 있는 모든 노드들의 최단 경로를 갱신합니다. 이 때, 기존 경로보다 더 짧은 경로를 발견하면 해당 ..