[백준 1753] 최단경로 (자바)

 

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

1753번: 최단경로

 

난이도 : 골드 5

 

다익스트라 알고리즘을 이용해 풀었습니다.

다익스트라 알고리즘은 음의 가중치가 없을 때 최단 경로를 탐색할 수 있습니다.

그중 저는 우선순위 큐를 이용하여 풀었습니다.

 

아래의 그래프는 1에서 출발할 때의 가중치의 값입니다.

그래프의 초기 상태

1을 방문하고 연결된 점들의 값을 업데이트

가장 작은 가중치를 가진 점인 2 방문 후 연결 가중치 업데이트 

최종 상태

1. 출발지 정점에서 연결된 정점의 가중치 값 입력
2. 방문하지 않았고 가장 작은 가중치의 값을 가지고 있는 정점 방문
3. 방문한 정점에서 연결된 정점들의 가중치 값 업데이트 minimum(연결된 정점의 현재 값, 현재 정점의 값 + 연결된 간선의 가중치)
4. 2~3 반복

이를 통해 다익스트라로 출발지로부터의 최소 비용을 구할 수 있습니다.

우선순위 큐를 사용하여 현재 가중치 값이 가장 작은 정점순으로 정렬합니다.

그 후 1~4를 통해 값을 구합니다.

---

전역 변수

LinkedList<Node> list[] = 문제에서 주어진 간선

int distance[] = 가중치의 값

boolean visit[] = 방문 확인 배열

 

함수

void main

입력을 받고 distance 배열을 -1로 세팅해줍니다. 최종적으로 이 배열에 -1이 있으면 연결되지 않은 정점입니다.(INF = Infinity)

간선의 입력을 받고 출발지로부터 다익스트라 알고리즘을 돌립니다.

(dijkstra 호출)

 

void dijkstra

우선순위 큐에 시작 정점을 넣어줍니다. 그리고 시작 지점의 가중치는 0입니다.

우선순위 큐가 빌 때까지 while문을 반복합니다.

현재 정점에 방문하지 않았을 때 연결된 정점들에 대해 검사를 시작합니다.

연결된 정점의 가중치가 -1이거나 연결된 정점의 가중치가 현재 정점의 가중치와 현재 간선의 가중치의 합보다 클 때 값을 업데이트합니다.

업데이트 후 다음 정점을 우선순위 큐에 넣어줍니다.

 

class Node

노드는 정점의 번호와 가중치를 가집니다.

우선순위 큐의 타입으로 이용하기 위해 Comparable을 implements 해줍니다.

정렬 기준은 가중치의 오름차순입니다.