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

백준 1753번 최단경로 (자바)

 

 

 

출처

www.acmicpc.net/problem/1753

1753번: 최단경로

 

 

 

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

 

 

 

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

 

 

 

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

 

 

 

 

입출력 예

입출력 예 1

 

 

 

걸린 시간

 

 

 

접근 방법

다익스트라의 기본 알고리즘을 활용하면 풀 수 있는 문제다.

 

기본적으로 사전에 준비가 필요한 부분은

1. 최단 경로 배열을 처음에는 무한대로 초기화해야하기 때문에 (int) 1e9로 초기화한다.

2. 트리 탐색에 필요한 List를 ArrayList로 생성한다.

3. 최단 경로 배열을 생성한다.

 

위 작업을 모두 마친 후 우선순위 큐를 이용해 다익스트라를 실행한다.

시작 노드는 거리가 0이므로 큐에 넣어주고 배열도 0으로 초기화한다.

 

큐에서 거리와 노드를 가져온 후 기존의 경로보다 현재 거리가 크다면 최단경로가 아니므로 해당 단계를 통과한다.

만약 아니면, 다른 노드로 가는 짧은 거리를 갱신시킨다.

 

이후에 i번째 최단경로가 무한으로 초기화되어있다면 INF를 출력하고, 아니면 최단경로를 출력한다.

 

 

 

 

내 코드

 

 

고려할 점

1. 다익스트라 알고리즘 사용할 것