[BaekJoon] 11404 플로이드 (Java)

1.  문제 링크

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

2.  문제

요약

• n개의 도시가 있고 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있습니다.
• 각 버스는 한 번 사용할 때 필요한 비용이 있습니다.
• 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 100보다 작거나 같은 도시의 개수 n이 주어지고 두 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 버스의 개수 m이 주어집니다. 세 번째 줄부터 m개의 줄에는 버스의 정보가 주어집니다.
  버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 100,000보다 작거나 같은 자연수인 한 번 타는데 필요한 비용 c로 이루어져 있습니다.
  • 시작 도시와 도착 도시가 같은 경우는 없습니다.
• 출력: 첫 번째 줄부터 n개의 줄에 필요한 최소 비용을 출력합니다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용입니다. 만약 i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int n, m;
	static HashMap<Integer, ArrayList<Edge>> map;
	static void input() {
		Reader scanner = new Reader();
		n = scanner.nextInt();
		m = scanner.nextInt();
		map = new HashMap<>();
		for(int i = 1; i <= n; i++) {
			map.put(i, new ArrayList<>());
		}
		for(int i = 0; i < m; i++) {
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			int c = scanner.nextInt();
			map.get(a).add(new Edge(b, c));
		}
	}
	
	static void solution() {
		for(int i = 1; i <= n; i++) {
			dijkstra(i);
		}
		System.out.println(sb.toString());
	}
	
	static void dijkstra(int start) {
		int[] distance = new int[n + 1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[start] = 0;
		Queue<Edge> queue = new LinkedList<>();
		queue.offer(new Edge(start, 0));
		while(!queue.isEmpty()) {
			Edge cur_edge = queue.poll();
			int cur_vertex = cur_edge.vertex;
			int cur_distance = cur_edge.distance;
			if(distance[cur_vertex] < cur_distance) continue;
			for(Edge e : map.get(cur_vertex)) {
				if(distance[e.vertex] > distance[cur_vertex] + e.distance) {
					distance[e.vertex] = distance[cur_vertex] + e.distance;
					queue.offer(new Edge(e.vertex, distance[e.vertex]));
				}
			}
		}
		for(int i = 1; i <= n; i++) {
			if(distance[i] == Integer.MAX_VALUE) sb.append(0).append(' ');
			else sb.append(distance[i]).append(' ');
		}
		sb.append('\n');
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
	static class Edge {
		int vertex, distance;
		public Edge(int vertex, int distance) {
			this.vertex = vertex;
			this.distance = distance;
		}
	}
}

4.  접근

• 해당 문제는 Floyd-Warshall 알고리즘을 이용하여 해결할 수 있습니다.
• 다익스트라 알고리즘을 연습하기 위해 다익스트라 알고리즘을 이용하여 풀어봤습니다.
• 주어진 버스 정보를 HashMap에 넣습니다. key는 시작 도시를 의미하고 value는 Edge라는 Class 형태의 ArrayList로 넣는데, Edge는 도착 도시를 나타내는 vertex와 도착 도시까지 필요한 비용을 나타내는 distance를 멤버 변수로 가집니다.
• 1번 도시부터 n번 도시까지를 각각 시작 도시로 놓고 다익스트라 알고리즘을 이용해 각 도시에서 다른 모든 도시들로의 최소 비용을 구합니다.
  • 시작 도시로부터 각 도시까지의 최소 비용을 나타내는 distance 배열을 생성하고 자기 자신에 대해서는 비용이 0이기 때문에 자기 자신은 0으로, 다른 도시들은 정수형의 최대값으로 값을 초기화합니다.
  • 탐색할 간선들을 넣을 Queue를 하나 생성하고 vertex를 출발 도시, distance를 0으로 하는 Edge를 Queue에 넣고 시작합니다.
  • Queue가 비워질 때까지 반복문을 돌며 각 도시들로의 최소 비용을 구합니다.
    • Queue에서 현재 탐색할 간선을 뽑고 그 간선의 vertex를 cur_vertex에, distance를 cur_distance에 넣어줍니다.
      • 만약 distance[cur_vertex]가 cur_distance보다 작다면 다음 탐색으로 넘어갑니다.
        • distance 배열이 현재까지의 탐색에서 각 도시로의 최소 비용을 나타내는데 이 값이 현재 탐색하는 간선의 distance인 cur_distance보다 작다면 현재 탐색하는 간선을 이용하여 도착 도시까지 갔을 때 distance 배열의 값보다 더 작아질 수 없기 때문에 distance 배열의 값이 갱신될 일이 없어 굳이 탐색할 필요가 없습니다.
      • 그렇지 않다면 cur_vertex와 이어져있는 간선들을 각각 확인하여 다음 탐색 때에 이용할 간선들을 Queue에 넣어줍니다.
        • cur_vertex와 이어져있는 간선의 도착 도시 위치에 해당하는 distance 배열의 값이 (cur_vertex 위치에 해당하는 distance 배열의 값 + cur_vertex와 이어져있는 간선의 비용)보다 크다면 cur_vertex와 이어져있는 간선을 이용하여 도착 도시에 가는 것이 더 적은 비용이 든다는 뜻이므로 distance 배열의 값을 갱신하고 cur_vertex와 이어져있는 간선의 도착 도시와 도착 도시의 distance 값을 이용하여 Edge 객체를 생성한 후에 이를 Queue에 넣어줍니다.