Baekjoon 11562번: 백양로 브레이크

 

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

11562번: 백양로 브레이크

백양로 브레이크~

플로이드 워셜 알고리즘을 이용해 풀었다. 플로이드 워셜 알고리즘은 시간 복잡도가 O(n^3)이지만 구현이 쉽다. 

 

 

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

//백양로 브레이크
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String[] sarr = str.split(" ");
		int n = Integer.parseInt(sarr[0]);
		int m = Integer.parseInt(sarr[1]);
		int[][] map = new int [n][n];
		
		for (int i = 0; i < n; i++) { // 행만큼만 반복
			Arrays.fill(map[i], 9999);
			map[i][i] = 0; // 자기자신 정점
		}
		
		int u = 0, v = 0, b = 0;
		for (int input = 0; input < m; input++) {
			str = br.readLine();
			sarr = str.split(" ");
			u = Integer.parseInt(sarr[0])-1;
			v = Integer.parseInt(sarr[1])-1;
			b = Integer.parseInt(sarr[2]);
			
			map[u][v] = 0;
			if(b == 0) {
				map[v][u] = 1;
			} else {
				map[v][u] = 0;
			}
		}//end of input for
		
		// 플로이드 워셜 
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = Math.min(map[i][j], map[i][k]+map[k][j]);
				}
			}
		}
		
		int k = Integer.parseInt(br.readLine());
		for (int output = 0; output < k; output++) {
			str = br.readLine();
			sarr = str.split(" ");
			int s = Integer.parseInt(sarr[0]) - 1;
			int e = Integer.parseInt(sarr[1]) - 1;
			System.out.println(map[s][e]);
		}
	}//end of main
}//end of class