[BaekJoon] 1753 최단경로 (Java)

1.  문제 링크

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

2.  문제

요약

• 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 20,000보다 작거나 같은 정점의 개수 V와 1보다 크거나 같고 300,000보다 작거나 같은 간선의 개수 E가 주어지고 두 번째 줄에 시작 정점의 번호 K가 주어지며 세 번째 줄부터 E개의 줄에 세 정수 u, v, w가 주어지는데 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻입니다.
  • u와 v는 서로 다르며 w는 10 이하의 자연수입니다.
• 출력: 첫 번째 줄부터 V개의 줄에 걸쳐 i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력합니다. 시작점 자신은 0으로 출력하고 경로가 존재하지 않는다면 INF를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Main {
	static HashMap<Integer, ArrayList<Edge>> map;
    public int[] getMinWeight(int start) {
		int[] weights = new int[map.size() + 1];
		Arrays.fill(weights, Integer.MAX_VALUE);
		weights[start] = 0;
		PriorityQueue<Edge> queue = new PriorityQueue<Edge>();
		queue.offer(new Edge(start, weights[start]));
		while(!queue.isEmpty()) {
			Edge cur_edge = queue.poll();
			int cur_vertex = cur_edge.vertex;
			int cur_weight = cur_edge.weight;
			if(weights[cur_vertex] < cur_weight) {
				continue;
			}
			for(Edge e : map.get(cur_vertex)) {
				if(weights[e.vertex] > weights[cur_vertex] + e.weight) {
					weights[e.vertex] = weights[cur_vertex] + e.weight;
					queue.offer(new Edge(e.vertex, weights[e.vertex]));
				}
			}
		}
		return weights;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int vertex_num = Integer.parseInt(input[0]);
		int edge_num = Integer.parseInt(input[1]);
		map = new HashMap<>();
		for(int i = 1; i <= vertex_num; i++) {
			map.put(i, new ArrayList<Edge>());
		}
		int start = Integer.parseInt(br.readLine());
		for(int i = 0; i < edge_num; i++) {
			input = br.readLine().split(" ");
			map.get(Integer.parseInt(input[0])).add(new Edge(Integer.parseInt(input[1]), Integer.parseInt(input[2])));
		}
		br.close();
		Main m = new Main();
		int[] weights = m.getMinWeight(start);
		for(int i = 1; i <= vertex_num; i++) {
			if(weights[i] == Integer.MAX_VALUE) {
				bw.write("INF\n");
			} else {				
				bw.write(weights[i] + "\n");
			}
		}
		bw.flush();
		bw.close();
	}
	
	public static class Edge implements Comparable<Edge> {
		int vertex;
		int weight;
		public Edge(int vertex, int weight) {
			this.vertex = vertex;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge e) {
			// TODO Auto-generated method stub
			return this.weight - e.weight;
		}
	}
}

4.  접근

• 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있습니다.
• 간선 정보를 나타내기 위해 도착 정점의 번호와 해당 간선의 가중치를 멤버 변수로 가지는 Edge 클래스를 생성합니다.
• 주어진 방향 그래프 정보를 이용하여 HashMap을 통해 그래프를 생성합니다.
• 시작 정점부터 각 정점까지 최단 경로에서의 가중치를 나타내는 배열 weights를 생성하고 값들을 모두 정수의 최댓값으로 초기화하는데 시작 정점에 대해서는 가중치가 0이므로 시작 정점의 값은 0으로 초기화합니다.
• 탐색하려는 정점 및 현재까지 해당 정점에서의 가중치를 나타내는 PriorityQueue를 생성하고 시작 정점에 대한 정보를 Queue에 넣어줍니다.
• Queue가 비워질 때까지 반복문을 돌며 Queue에서 정점을 하나씩 꺼내고 만약 해당 정점에서의 weights 값이 Queue에서 꺼낸 가중치 값보다 작다면 값을 갱신해줄 필요가 없기 때문에 다른 작업을 하지 않습니다.
• 만약 그렇지 않다면 해당 정점과 이어져있는 간선들을 확인하며 만약 각 간선의 도착 정점의 weights 값이 (Queue에서 꺼낸 정점에서의 weights 값 + 각 간선의 가중치)보다 크다면 Queue에서 꺼낸 정점에서 각 간선의 도착 정점으로 가는 것이 최단 경로가 되기 때문에 이 값으로 weights 값을 갱신시키고 Queue에 해당 도착 정점에 대한 정보를 넣어줍니다.