[백준] 11404 플로이드

문제

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

11404번: 플로이드

문제 정리

1<= n <= 100 : 도시
1<= m <= 100,000 : 한도시에서 출발해서 다른 도시에 도착하는 버스의 수
버스의 정보
 - a : 시작 도시
 - b : 도착 도시
 - c : 필요한 비용

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값 구하기!

 

소스코드

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

public class Main_11404_플로이드 {
	static int n,m;
	static int map[][];
	static final int MAX_VALUE = 123456789;
	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		n = Integer.parseInt(in.readLine());
		m = Integer.parseInt(in.readLine());
		
		map = new int[n][n];
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			int c = Integer.parseInt(st.nextToken());
			
			map[a][b] = map[a][b]==0? c : Math.min(c, map[a][b]);
			
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = map[i][j] == 0? MAX_VALUE : map[i][j];
			}
		}
		
		//풀이 
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				if(k==i) continue;
				for (int j = 0; j < n; j++) {
					if(k==j || i==j) continue;
					
					if(map[i][k]!= MAX_VALUE 
							&& map[k][j] != MAX_VALUE
							&& map[i][j] > map[i][k] + map[k][j]) {
						map[i][j] = map[i][k] + map[k][j];
					}
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int a = map[i][j] == MAX_VALUE? 0 : map[i][j];
				sb.append(a + " ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
}

소스 코드 풀이

1. 입력 시 동일한 정점이 여러번 들어올 수 있다 -> 최솟값으로 넣어주기

2. 입력이 끝난 후 map의 값이 0인 지점은 MAX_VALUE로 채워줘서 최소비용을 못 만들도록 하기 

3. k라는 변수로 중간 정점을 만들어서 계속 비교비교! 

if(map[i][k]!= MAX_VALUE && map[k][j] != MAX_VALUE && map[i][j] > map[i][k] + map[k][j]) {
	map[i][j] = map[i][k] + map[k][j];
}

이 코드가 메인이라고 할 수 있다.

4. 입력이 많을 수 있기 때문에 StringBuilder에 저장한 후 출력

Review

- 플로이드 와샬 오랜만에 본다.

플로이드 와샬은 시간 복잡도가 n^3 인 대신 모든 정점에서의 최소 비용을 구할 수 있다는 장점이 있다. 중간 정점을 세워서 최소비용을 비교한다는 개념만 어느정도 숙지가 되면 쉽게 사용할 수 있는 것도 큰 장점이다. input 에서 문제를 제대로 안 읽어서 동일한 정점이 들어오는 걸 모르고 착각해서 좀 시간을 날렸다... 문제를 잘 읽어야지!

다음주에는 MST위주로 풀어봐야 겠다:)