[JAVA] 백준 11404번 플로이드

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

11404번: 플로이드

백준 문제 링크입니다.

문제 난이도는 solved.ac에 골드 4 난이도로 되어 있습니다.

 

이 문제는 플로이드-워셜 알고리즘을 활용해 푸는 문제입니다.

---

문제를 간단히 설명하면,

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B까지 가는데 필요한 비용의 최솟값을 구하는 문제입니다.

A와 B는 같은 도시가 될 수 없으며, 중간에 다른 도시를 거쳐 가도 됩니다.

 

[입력 조건]

도시의 개수 N (2 <= N <= 100)

버스의 개수 M (1 <= M <= 100,000)

비용 C (1 <= C <= 100,000)

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있습니다.

즉, 노선이 같은 버스가 2개 이상일 수 있습니다.

 

[출력]

NXN 행렬을 출력합니다.

i행 j열에 출력하는 숫자는 도시 i에서 j까지 가는데 필요한 최소 비용입니다.

만약, i에서 j로 갈 수 없는 경우는 0을 출력합니다.

 

[코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class B11404_2 { //플로이드
	static int[][] map;
	static final int INF = Integer.MAX_VALUE >> 1;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		map = new int[N + 1][N + 1];
		for(int[] arr : map) Arrays.fill(arr, INF);

		for(int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			//시작 도시에서 도착 도시까지 한번에 가는 값 저장
			if(map[start][end] > cost) map[start][end] = cost;
		}
		
		//v : 환승 지점, s : 출발 지점, e : 도착 지점
		for(int v = 1; v <= N; v++) {
			for(int s = 1; s <= N; s++) {
				if(s == v) continue;
				
				for(int e = 1; e <= N; e++) {
					if(s == e || e == v) continue;
					
					//저장되어 있던 가장 최소값과 탐색하고 있는 값 중 작은 값 저장
					map[s][e] = Math.min(map[s][e], map[s][v] + map[v][e]);
				}
			}
		}
		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) sb.append(map[i][j] == INF ? 0 : map[i][j]).append(" ");
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
}

[사진 1] 플로이드-워셜 결과

---

플로이드-워셜(Floyd-Warshall)과 다익스트라(Dijkstra)

잠깐 플로이드-워셜과 다익스트라 알고리즘의 개념을 간단하게 짚고 넘어가겠습니다.

플로이드-워셜 : 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
다익스트라 : 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

 

V : 정점

E : 간선

다익스트라를 우선순위 큐로 구현했을 때 플로이드-워셜과의 차이를 보겠습니다. 

	플로이드-워셜	다익스트라(우선순위 큐)
시간 복잡도	V^3	ElogV
공간 복잡도	V^2	V+E
음의 가중치	O	X
음의 사이클	X	X

 

다익스트라 알고리즘으로 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하면,

ElogV를 V개 해야되니 시간 복잡도가 V*(ElogV)가 나올 것 입니다.

 

V와 E의 크기에 따라 시간복잡도를 고려하면서 어떤 알고리즘으로 코드를 작성할 지 정하면 됩니다.

 

11404 문제는 모든 도시에서 다른 모든 도시까지의 최단 경로를 구하는 문제입니다.

V의 범위가 100 이하, E의 범위가 100,000 이하이기 때문에 어떤 알고리즘으로 구현해도 정답이 나옵니다.

 

아래 코드는 다익스트라로 해결한 코드입니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class B11404_1 { //플로이드
	static ArrayList<Node>[] map; //노선도
	static int[][] dis; //가장 짧은 거리
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		//초기화
		map = new ArrayList[N + 1];
		for(int i = 1; i <= N; i++) map[i] = new ArrayList<>();
		dis = new int[N + 1][N + 1];
		
		//map에 노선 추가
		for(int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			map[start].add(new Node(end, cost));
		}
		
		//dis의 모든 값 최대치로 설정
		for(int[] arr : dis) Arrays.fill(arr, Integer.MAX_VALUE);
		
		for(int s = 1; s <= N; s++) {
			PriorityQueue<Node> PQ = new PriorityQueue<>();
			boolean[] vis = new boolean[N + 1];
			
			dis[s][s] = 0;
			PQ.add(new Node(s, 0));
						
			while(!PQ.isEmpty()) {
				Node cur = PQ.remove();
				int v = cur.bus;
				
				if(vis[v]) continue;
				vis[v] = true;
				
				//현재 정거장에서 갈 수 있는 모든 정거장 탐색
				for(Node node : map[v]) {
					int e = node.bus, cost = node.cost;
					
					//출발 정거장에서 다음 정거장까지 가는 가장 짧은 값 - A
					//출발 정거장에서 현재 정거장까지 가는 가장 짧은 값 + 현재 정거장에서 다음 정거장까지 가는 비용 - B
					//A > B 라면 B를 dis[s][e]에 저장
					if(dis[s][e] > dis[s][v] + cost) {
						dis[s][e] = dis[s][v] + cost; //B를 dis[s][e]에 저장
						PQ.add(new Node(e, dis[s][e]));
					}
				}
			}
		}
		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				if(dis[i][j] == Integer.MAX_VALUE) sb.append("0").append(" ");
				else sb.append(dis[i][j]).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
	
	static class Node implements Comparable<Node>{
		int bus, cost;
		
		Node(int bus, int cost) {
			this.bus = bus;
			this.cost = cost;
		}

		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return this.cost - o.cost;
		}
	}
}

[사진 2] 다익스트라 결과

[사진 1]과 [사진 2]를 비교하면 플로이드-워셜 알고리즘으로 구현한 [사진 1]이 더 빠른 것을 알 수 있습니다.

 

이처럼 V의 크기가 작을 때는 플로이드-워셜이 더 효율적인 것을 볼 수 있습니다.

구현 자체도 플로이드-워셜이 더 간단해서 V의 범위가 500 이하라면 플로이드-워셜로 구현하면 됩니다.

---

플로이드-워셜

모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘입니다.

이 알고리즘은 거쳐가는 정점을 기준으로 구현해야 합니다.

 

우선 모든 행열을 INF로 초기화 해주고 입력 받은 값들 중에서 최소값을 행열에 저장해줍니다.

		map = new int[N + 1][N + 1];
		for(int[] arr : map) Arrays.fill(arr, INF);

		for(int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			//시작 도시에서 도착 도시까지 한번에 가는 값 저장
			if(map[start][end] > cost) map[start][end] = cost;
		}

 

그리고 거쳐가는 정점을 기준으로 출발 지점과 도착 지점의 최단 경로를 구합니다.

		//v : 환승 지점, s : 출발 지점, e : 도착 지점
		for(int v = 1; v <= N; v++) {
			for(int s = 1; s <= N; s++) {
				if(s == v) continue;
				
				for(int e = 1; e <= N; e++) {
					if(s == e || e == v) continue;
					
					//저장되어 있던 가장 최소값과 탐색하고 있는 값 중 작은 값 저장
					map[s][e] = Math.min(map[s][e], map[s][v] + map[v][e]);
				}
			}
		}

코드로 설명한다면 v를 기준으로 s와 e를 반복합니다.

 

이때, v의 위치를 s나 e와 바꾸게 된다면 잘못 구현한 것입니다.

v가 기준점이 되지 않는다면 v를 거쳐가는 도시가 누락될 수 있습니다.

 

반복문이 종료됐으면 map을 출력하면 결과입니다.

---

제가 공부한 부분을 정리한 내용이기 때문에 틀린 부분 있을 수 있습니다!!

혹시 틀린 부분이 있으면 알려주세요!!