[백준] 11404번 - "플로이드" (Java)

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

11404번: 플로이드

플로이드

---

 

난이도 :  골드 4

 

 플로이드-와샬 기본 문제입니다. 

 

 

 주의 사항은 INF를 Integer.MAX_VALUE로 설정하면 안 됩니다. 상황에 따라 오버플로우가 발생할 수 있기 때문입니다. 

INF는 간선 가중치의 최댓값 * 정점 개수 -1 보다 큰 값을 사용하면 됩니다.

 

 

- static int map [][];

 각 정점들 사이의 최소 비용을 저장할 이중 배열입니다. 

 

 

 

- static final int INF = 9900001;

 map 배열의 초기 값으로 설정할 INF입니다. 가중치의 최댓값은 100,000이고 정점 개수는 100개입니다. 

INF는 100,000 * 99 이상의 값을 설정하면 됩니다. 

 

 

 

- void main()

 입력을 처리하고 map 배열을 초기화합니다. 그다음 주어진 정보로 각 도시를 연결합니다. 여기서 주의할 점은 시작 도시와 도착 도시를 연결하는 노선이 여러 개일 확률을 고려하여 최솟값을 저장하도록 합니다. 

 

 플로이드 와샬 함수를 호출하고 출력문을 통하여 답을 도출합니다. 

 

 

 

- void floydWarshall(int n)

 플로이드 - 와샬 알고리즘을 수행하는 함수입니다. 주어진 n개의 도시를 기준으로 탐색합니다. 

 

 

  코드

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

public class Main{
	// BOJ / 11404번 / 플로이드- 와샬   / 플로이드
	static int map[][];
	static final int INF = 9900001;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk;
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		map = new int[n+1][n+1];
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				// 자기 자신은 0, 아니면 INF로 초기화
				if(i==j) continue;
				else map[i][j] = INF;
			}
		}
		
		for(int i=0; i<m; i++) {
			stk = new StringTokenizer(br.readLine(), " ");
			int s = Integer.parseInt(stk.nextToken());
			int e = Integer.parseInt(stk.nextToken());
			int w = Integer.parseInt(stk.nextToken());
			// 시작 도시와 도착 도시를 연결하는 노선이 여러 개일 확률을 고려하여 최솟값 저장.
			map[s][e]= Math.min(w, map[s][e]); 
		}
		
		floydWarshall(n);
		StringBuilder sb = new StringBuilder();
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(map[i][j] == INF) {
					sb.append("0 ");
				}
				else sb.append(map[i][j] + " ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
	
	public static void floydWarshall(int n) {
		
		for(int k=1; k<=n; k++) { // 경유지 
			for(int i=1; i<=n; i++) { // 출발지
				if(i==k) continue;
				for(int j=1; j<=n; j++) { // 도착지 
					if(i==j || j==k) continue;
					if(map[i][j] > map[i][k]+ map[k][j]) {
						map[i][j] = map[i][k] + map[k][j];
					}
				}
			}
				
		}
	}

}

 

 

 

 

 

피드백 환영합니다.