[백준 1753] 최단경로 -Java코드 (Dijkstra)★★★

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

1753번: 최단경로

 

문제

 

설계

이 문제는 그래프의 최소경로값을 구하는 문제이다.

최소경로 문제는 BFS, Floyd Warshall(플로이드 와샬), 다익스트라(Dijkstra) 알고리즘 등으로 풀 수 있다.

 

가중치 개념이 없는 단순 최소경로문제   ->   BFS
가중치 개념이 있는 한 노드기준의 최소경로값   ->   Dijkstra (다익스트라)
가중치 개념이 있는 모든 노드기준의 최소경로값   -> Floyd Warshall(플로이드 와샬),

 

가중치 개념이 존재하면서 기준점에 대해 최소값을 구해야 하므로 다익스트라를 이용한다.

다익스트라를 구현할 때 인접 행렬, 인접 리스트 둘 다 구현할 수 있는데

 1 ≤ V ≤ 20,000

1 ≤ E ≤ 300,000 

input값이 위와 같기 때문에, 인접행렬을 만드는것보다 List를 이용하는게 효율적이다.

 

이해

문제를 잘 이해 해야하는게 

예제에서 1과 5가 이어진걸로 보지않고 INF값이 나온것을 통해 단방향성 연결이라는걸 이해할수 있다.

 

또한, 

시작점이 주어지면, 그 지점을 기준으로  가중치값을 더해가면서 최소경로를 구해주기만 하면된다.

모든 노드별로 최단거리를 구하는 문제가 아니므로 조금 더 쉬운것이다.

 

그리고

다익스트라는 최단경로를 구할때쓰는데, 주의할건 인접행렬이나 인접리스트를 구해가는 과정에서

우선순위 큐를 이용해 최소값 기준으로 탐색하도록해야 효율성이 올라간다는점이다.

그런점에서 이 문제는 다익스트라라는 복잡한 알고리즘에 기본구조를 이해하기 좋다. 

 

풀이

// 133928 KB 	1236 ms
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.stream.Stream;

/*
 * 다익스트라는 그래프에서 간선에 가중치가 존재할때 사용됨
 * 인접매트릭스, 인접리스트 둘 중하나를 input range에 따라 적절히 사용
 * 입력범위가크므로 리스트를 이용해서 품
 * */
//시작점에 연결된 간선을 저장할 클래스선언
class Edge implements Comparable<Edge>{
	int i, v;
	public Edge(int i, int v) {
		this.i = i;
		this.v = v;
	}
	// 우선순위 큐에서 사용시 최솟값 정렬
	@Override
	public int compareTo(Edge o) {
		return this.v - o.v;
	}	
}
public class Main{
	// 전역적 접근이 필요한 변수 - 인접리스트 list, 결과거리 dist
	static ArrayList<Edge> list[];
	static int dist[]; 
	
	public static void main(String[] args) throws IOException {
		// Scanner보다 BuggeredReader가 빠르고 효율적임
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// input 받기
		int[] in = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); 
		int dot = in[0], line=in[1];
		int start = Integer.parseInt(br.readLine());
		
		// input 받기 - 연결정보 저장
		list = new ArrayList[dot+1]; // 편의상 0번은 사용하지 않을것이므로 +1
		for(int i=1;i<list.length;i++) 
			list[i] = new ArrayList<Edge>();
		for(int i=0;i<line;i++) {            
			String [] tt = br.readLine().split(" ");
	        int a = Integer.parseInt(tt[0]);    //노드1
	        int b = Integer.parseInt(tt[1]);    //노드2
	        int w = Integer.parseInt(tt[2]);    // 거리
	        list[a].add(new Edge(b,w));		
		}
			
		
		// start부터 각 dot으로 가는 최단거리를 저장할 결과배열 dist 선언 및 초기화
		dist = new int[dot+1]; //input 특성상 0번을 사용하지 않으므로 + 1
		Arrays.fill(dist, Integer.MAX_VALUE); // 최솟값을 구해야하므로 MAX값으로 초기화
		dist[start] = 0; // 시작점 거리값
		
		// 다익스트라로 start에서 연결된 모른 경로값을 탐색
		dijkstra(start);
		
		// 결과 출력문 (0번 제외)
		for(int i=1;i<dist.length;i++) {
			if(dist[i]== Integer.MAX_VALUE)
				System.out.println("INF");
			else
				System.out.println(dist[i]);
		}
	}
	private static void dijkstra(int s) {
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>(); //pq를 사용하면 최소값 기준으로 들어가기 때문에 연산이 줄어든다
		pq.add(new Edge(s,0)); // 탐색 시작점
		
		while(!pq.isEmpty()) {
			Edge now = pq.poll();
			// 탐색할 점에 연결된 정보기반으로 dist 갱신
			for(Edge next : list[now.i]) {
				if(dist[next.i] > now.v + next.v) {
					dist[next.i] = now.v + next.v;
					pq.add(new Edge(next.i, dist[next.i]));
				}
			}			
		}
	}
}
/*
==============  input ==============
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
============== output ==============
0
2
3
7
INF

 */

 

다익스트라에서는 가중치값까지 저장되야하므로

Node Class에 대한 생성이 필요하고,

PriorityQueue 의 특성상 Node Class 가 가중치 기준으로 정렬되기 위해서는

해당 클래스에서 Comparable 상속 후 compareTo 메소드에 대한 구현이 필요하다는걸 기억하자! 

+

추가적으로 인접 리스트에 대한 2차원적인 초기화도 잘 기억해두자.  (ArrayList 배열 선언)