[JAVA]백준 11404번: 플로이드

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

11404번: 플로이드

 

 

| 문제 해결방법

 

이 문제는 제목에서 대놓고 힌트를 주고 있다.

플로이드-워셜 알고리즘으로 문제를 풀면 된다.

 

 

 

기본적인 플로이드-워셜 문제와 거의 동일하다.

한 가지 다른 점은 예제를 한 번 손으로 적으면서 돌려보면 알 수 있는데,

같은 간선에 비용만 다른 경우가 존재한다.

 

이 경우 우리가 하려고 하는 값은 최소 비용이기 때문에 

작은 비용을 선택해주면 된다. 

 

 

 

그리고 내가 두 번이나 틀렸던 이유로 

플로이드-워셜 알고리즘을 돌린 후 바로 그냥 출력을 해버린 실수가 있었다.

 

★갈 수 없는 정점은 처음에 초기화 한 INF값을 가지고 있기 때문에 0으로 바꿔서 출력해주어야 한다 ★

 

 

 

[JAVA] 해설 코드

package graph.bfs_dfs;

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

public class BOJ_11404 {

	static int N, bus;
	static int INF = 987654321;
	static int[][]arr;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		bus = Integer.parseInt(br.readLine());
		arr = new int[N+1][N+1];

		// 간선이 없는 경우는 INF, i==j인 경우는 0 
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				if(i==j)
					arr[i][j]=0;
				else {
					arr[i][j] = INF;
				}
			}
		}
		
		for(int i=0;i<bus;i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			// 이미 해당 간선에 비용이 저장되어있는 경우 
			if(arr[s][e]!=0) {
				// 최솟값을 선택해 저장
				arr[s][e] = Math.min(arr[s][e],cost);
			}else {				
				arr[s][e] = cost;
			}
		}
		
		// 플로이드-워셜 알고리즘 
		for(int k=1;k<=N;k++) {
			for(int i=1;i<=N;i++) {
				for(int j=1;j<=N;j++) {
					if(arr[i][k] + arr[k][j] < arr[i][j]) {
						arr[i][j] = arr[i][k] + arr[k][j];
					}
				}
			}
		}
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				// 갈 수 없는 길인 경우는 0 출력
				if(arr[i][j] ==INF)
					sb.append(0).append(" ");
				else
					sb.append(arr[i][j]).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
		
	}
	
}

 

 

 

[제출] 메모리 및 시간