백준 골드 4 최단경로 1753

https://www.acmicpc.net/problem/1753

 

 

문제 분석 후 예제 입력 이해 

 

 

 

문제 분석

 

시작점과 다른 노드와 관련된 최단 거리를 구하는 문제로,

다익스트라 알고리즘의 가장 기본적인 형태를 구현할 수 있는지를 묻고 있다.

다익스트라 알고리즘을 코드로 구현할 수 있는가? 를 묻는 문제이다.

 

 

손 코딩 해보기

 

인접 리스트에 노드를 저장하고 거리 배열을 초기화한다.

거리 배열은 출발 노드는 0, 나머지는 무한으로 초기화하면 된다.

INF => 무한이라는 의미이니까.

 

최초 시작점을 큐에 삽입하고, 다음 과정에 따라 다익스트라 알고리즘을 수행한다.

 

---

다익스트라 알고리즘 수행 과정

 

① 거리 배열에서 아직 방문하지 않는 노드 중 현재 값이 가장 작은 노드를 선택한다.

② 해당 노드와 연결된 노드들의 최단 거릿값을 다음 공식을 이용해 업데이트한다.

• [연결 노드 거리 배열값]보다 [선택 노드의 거리 배열값 + 에지 가중치]가 더 작은 경우 업데이트 수행
• 업데이트가 수행되는 경우 연결 노드를 우선순위 큐에 삽입

③ 큐가 빌 때까지 ①~②을 반복한다.

 

         

 

---