11404번 - 플로이드

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

11404번: 플로이드

 

 

 

 

 

문제의 제목에서 알 수 있듯이 플로이드-와샬 알고리즘을 쓰는 문제이다. 골드4라는데 다른 골드 문제에 비하면 덜 까다로운 편이였다. 플로이드-와샬 알고리즘을 잘 알고 문제의 조건만 잘 처리를 하면 되기 때문에 같은 그래프 탐색의  DFS&BFS 문제보다 상대적으로 쉽게 느껴진다.

 

 

문제의 조건들을 꼼꼼히 읽어야 한다.

"시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다", "만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다."에 유의해야 한다.

 

99%쯤에서 문제가 틀리는 경우가 발생했는데 질문 게시판에서 같은 문제를 가지고 있는 글과 답변을 찾아서 보니 INF를 작은 수로 설정해서 그렇다고 한다. 완전히 큰 수로 바꿔줬더니 맞았다고 나온다.

 

 

 

 

 

코드

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

public class Floyd_warshall {
	static int INF = 987654321;
	
	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());
		
		int[][] arr = new int[n + 1][n + 1];
		
		for(int i = 1; i < n + 1; i++) { //배열 초기화
			for(int j = 1; j < n + 1; j++) {
				if(i == j) {
					arr[i][j] = 0;
					continue;
				}
				arr[i][j] = INF;
			}
		}
		
		for(int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			arr[a][b] = Math.min(arr[a][b], c);
		}
		
		for(int k = 1; k < n + 1; k++) { //플로이드-와샬
			for(int i = 1; i < n + 1; i++) {
				for(int j = 1; j < n + 1; j++) {
					arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
				}
			}
		}
		
		for(int i = 1; i < n + 1; i++) { //출력
			for(int j = 1; j < n + 1; j++) {
				if(arr[i][j] == INF) {
					arr[i][j] = 0;
				}
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}
	}

}

 

 

 

 

 

결과