[백준] 11562 백양로 브레이크 [JAVA]

문제링크 : https://www.acmicpc.net/problem/11562

11562번: 백양로 브레이크

플로이드 워셜 알고리즘에 대해 이해하고 있어야한다.

A 와 B 사이의 간선이 양방향일 경우 거리는 0이며, A->B로 단방향일 경우 A->B의 거리는 0, B->A의 거리는 1이다.

X -> Y로 갈 때 최소의 거리(단방향 도로를 양방향으로 바꾸는 비용)를 최대 3만번 구해야 한다. 건물의 수는 최대 250개 이므로 플로이드 워셜 알고리즘을 활용해서 최소 거리를 미리 구해놓고 해결했다

import java.io.*;
import java.util.*;
public class Main {
	public static int N,M;
	public static int dist[][];
	public static void main(String[] args) throws Exception{
		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		dist = new int[N+1][N+1];
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++){
				dist[i][j] = 987654321;
				if(i==j) dist[i][j] = 0;
			}
		}
		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			if(c==0){
				dist[a][b] = 0;
				dist[b][a] = 1;
			}else{
				dist[a][b] = 0;
				dist[b][a] = 0;
			}
		}
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++){
				if(i==j) continue;
				for(int k=1;k<=N;k++){
					if(i==k || j ==k) continue;
					if(dist[j][k] > dist[j][i] + dist[i][k]){
						dist[j][k] = dist[j][i] + dist[i][k];
					}
				}
			}
		}
		int query = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<query;i++){
			st = new StringTokenizer(br.readLine());
			int a= Integer.parseInt(st.nextToken());
			int b= Integer.parseInt(st.nextToken());
			sb.append(dist[a][b] + "\n");
		}
		System.out.println(sb.toString());
	}

}