11404_플로이드 **

사용 알고리즘: 플로이드 워셜

사용 언어: java

 

package week33;

import java.io.*;
import java.util.*;

public class Main {
	static int[][] dp ;
	static int n, m;

	public static void main(String[] args) throws IOException {
		init();
		
		for (int k = 1; k < n+1; k++) {
			for (int i = 1; i < n+1; i++) {
//				if(i == j) continue;
				for (int j = 1; j < n+1; j++) {
//					if(i == j) continue;
					//직행: dp[i][j]
					//경유: dp[i][k] + dp[k][j]
					if(dp[i][j] > dp[i][k] + dp[k][j]) {
						dp[i][j] = dp[i][k] + dp[k][j];
					}
				}
			}
		}
		
		//답
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < n+1; j++) {
				if(dp[i][j] == 987654321) {
					System.out.print(0+" ");
					continue;
				}
				System.out.print(dp[i][j]+" ");
			}
			System.out.println();
		}
		
	}

	private static void init() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); //도시 개수
		m = sc.nextInt(); // 버스 개수
		dp = new int[n+1][n+1];
		for (int i = 0; i < n+1; i++) {
			Arrays.fill(dp[i], 987654321);
		}
		for(int i=0; i<n+1; i++) {
			dp[i][i] = 0;
		}
		
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int cost = sc.nextInt();
			
			dp[a][b] = Math.min(dp[a][b], cost);
		}
	}

}

 

플로이드 워셜을 사용했는데 특정 케이스에서 풀리지 않는다면 이렇게 시도해보기!

1. k를 최상위 for문으로 바꾼다.

 => 플로이드 워셜은 경유하는 곳이 있는지를 확인하는 것!

 => 경유점을 먼저 지정하고, 그 경유점에 따라 출발/도착 위치를 바꾸면서 찾아보자

 

2. 초기 dp 배열의 값을 적당히 크게 설정한다.

  => 마구잡이로 Integer.MAX_VALUE를 사용하면, 더하는 과정에서 오버플로 때문에 음수가 될 수 있다.

  => 한 경로의 최대 cost와 나올 수 있는 경로의 수를 잘 조합하면 적당히 큰 수가 나올 수 있을듯.?