[JAVA] BOJ(백준) - 플로이드 - 11404

문제내용

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

11404번: 플로이드

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

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

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

---

문제 접근 방법

n개의 노드가 있을때 모든 n개의 노드까지 최소비용을 구하는 문제이고

각간선에 의한 음의 사이클이 없기 때문에 플로이드 알고리즘을 활용하면된다.

 

플로이드 알고리즘을 간략하게 말해보자면

전체 노드개수 n개일때
1번노드에서 출발해 1~n번 까지 노드까지 최소비용 구하기 
2번노드에서 출발해 1~n번 까지 노드까지 최소비용 구하기 
3번노드에서 출발해 1~n번 까지 노드까지 최소비용 구하기 
                                  ....

n-2번노드에서 출발해 1~n번 까지 노드까지 최소비용 구하기 

n-1번노드에서 출발해 1~n번 까지 노드까지 최소비용 구하기 
n번노드에서 출발해 1~n번 까지 노드까지 최소비용 구하기 

위의 말처럼 1~n번노에서 n번노드까지 최소비요을 모두 구하는 알고리즘이다.

 

다만 이문제에서 주의 해야할점 2가지가만 짚고 넘어가자.

1. 방향성
   이문제의 경우 간선은 A->B로 출발도시와 도착도시가 있다.
   따라서 간선의 방향성이 존재한다는걸 인지하고 풀어야한다.
   
   
2. 오버플로
   최소비용을 저장하기 위한 배열을 초기화할 때 일단 자기자신의 노드까지 거리는 0으로 초기화 한뒤,
   보통은 자기자신 노드가아닌 다른 노드로 향하는 값의 경우 후에 최소비용을 갱신해줘야 하기 때문에 Integer.MAX_VALUE 로 초기화 하게된다.
   여기서 주의할점이 있는데 플로이드 알고리즘을 구현할때
   

   	for(int k=1; k<=n; k++) {//k = 거처가는 노드
   			for(int i=1; i<=n; i++) {//i = 출발노드
   				for(int j=1; j<=n; j++) {//j = 도착노드
   					int firstV = dist[i][k];//i에서 출발해서 k까지 최소비용
   					int secondV = dist[k][j];//k에서 시작해서 j까지 최소비용
   					if(firstV == Integer.MAX_VALUE && secondV > 0) continue;//오버플로 예방
   					else if(secondV == Integer.MAX_VALUE && firstV > 0) continue;//오버플로 예방
   					else dist[i][j] = Math.min(dist[i][j], firstV+secondV);//오버플로 안나면 최솟값 갱신
   					
   					//참고-> dist[i][j]:i노드에서 j노드로 바로 감.
   					//   -> dist[i][k] + dist[k][j]: i노드에서 k노드 거친다음 j노드로 감.
   				}
   			}
   		}​

   위와 같이 구현하게 된다.
   근데 자바는 정수형의 최댓값에서 뭔가를 더했을때 정수형 최솟값으로 돌아가 작업하는 현상이 발생한다. 이를 오버플로라 하고 반대는 언더플로라고한다. 
   어쨌든 위의 코드에서 오버플로를 예방하기 위해 분기분으로 k노드를 거처간 값의 합이 Integer.MAX_VALUE 를 넘지 않도록 구현해야한다.
   
   

그외에 플로이드 알고리즘에 대한 자세한 내용은 아래 링크에 나와있으니 참고 바란다.
https://sskl660.tistory.com/61 

[Java]플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

---

풀이

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

public class Main {
	static int[][] dist; //dist[i][j] -> i번노드에서 j번노드까지 거리최소비용 배열
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine()); //노드 개수
		int m = Integer.parseInt(br.readLine()); //간선 개수
		dist = new int[n+1][n+1];
		
		//자기 자신 까지 거리는 0으로
		//그외는 ㅈㄴ 큰값으로 초기화 --> 최소비용으로 나중에 갱신해주기 위해.
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(i==j) dist[i][j]=0;
				else dist[i][j]=Integer.MAX_VALUE;
			}
		}
		
		//간선 개수 만큼돌면서 v1노드에서 v2노드까지 비용 초기화
		//방향성 있음.
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			//현재 바로 갈수 있는 노드들은 비용 최솟값으로 초기화.
			dist[v1][v2] = Math.min(dist[v1][v2], cost);
		}
		
		floyd(n,m); //플로이드ㄱㄱ 
		printAll(n);//정답 출력
	}
	
	/* 전체 노드개수 n개일때
	 * 1번노드에서 출발해 1~n번 까지 노드까지 최소비용 구하기 
	 * 2번노드에서 출발해 1~n번 까지 노드까지 최소비용 구하기 
	 * 3번노드에서 출발해 1~n번 까지 노드까지 최소비용 구하기 
	 * 					....
	 * n번노드에서 출발해 1~n번 까지 노드까지 최소비용 구하기 
	 */
	public static void floyd(int n, int m) {
		for(int k=1; k<=n; k++) {//k = 거처가는 노드
			for(int i=1; i<=n; i++) {//i = 출발노드
				for(int j=1; j<=n; j++) {//j = 도착노드
					int firstV = dist[i][k];//i에서 출발해서 k까지 최소비용
					int secondV = dist[k][j];//k에서 시작해서 j까지 최소비용
					if(firstV == Integer.MAX_VALUE && secondV > 0) continue;//오버플로 예방
					else if(secondV == Integer.MAX_VALUE && firstV > 0) continue;//오버플로 예방
					else dist[i][j] = Math.min(dist[i][j], firstV+secondV);//오버플로 안나면 최솟값 갱신
					
					//참고-> dist[i][j]:i노드에서 j노드로 바로 감.
					//   -> dist[i][k] + dist[k][j]: i노드에서 k노드 거친다음 j노드로 감.
				}
			}
		}
	}
	
	//출력
	public static void printAll(int n) {
		StringBuilder sb = new StringBuilder();
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(dist[i][j]==Integer.MAX_VALUE) sb.append(0).append(" ");
				else sb.append(dist[i][j]).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}
}

---

마무리

다익스트라 알고리즘과 비슷한면이 있지만
다익스트라 알고리즘의 경우 하나의 노드에서 각 모든 노드까지의 최단거리를 구한다면
플로이드 알고리즘의 경우 n개의 노드에서 각 모든 노드까지의 최단거리를 구할수 있다는 점이 다르다.

또한 
플로이드의 경우 다익스트라와 다르게 음에 가중치가 있어도 되지만 음의 사이클은 없어야한다는 것도 알아두자.
마지막으로 N개의 노드에대해 NxN배열을 확인하기 때문에 시간복잡도가 O(N^3) 걸리기 때문에 데이터 값이 많은지 적은지 확인하고 써야한다.