[백준 11562] 백양로 브레이크 (Java)

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

11562번: 백양로 브레이크

1. 주의할 점

- 매 쿼리마다 통행을 바꿔야하는 횟수를 구하지 않는다

 

2. 구현

- Arr[][] 배열을 통해 간선에 대한 정보를 받으며, Arr[a][b]는 a->b로 가기 위해 바꿔야 하는 도로의 수를 저장한다

- Arr[][] 배열을 초기화하고, 입력받을 때 단방향인 경우에는 0,1을 저장하고 양방향인 경우에는 0,0을 저장한다

- 플로이드 와샬 알고리즘을 통해 Arr[][] 배열을 미리 갱신시킨다

- 쿼리가 들어올때 마다 Arr[][] 배열의 값을 출력시킨다

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

class Main {
    static final int maxi = 251*251;
    static int node,edge,query;
    static int arr[][];
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine().trim();
	    StringTokenizer st = new StringTokenizer(str);
	    node = Integer.parseInt(st.nextToken());
	    edge = Integer.parseInt(st.nextToken());
	    
	    //초기화
	    arr = new int[node+1][node+1];
	    for(int i=1;i<=node;i++)
	        for(int j=1;j<=node;j++){
	            arr[i][j]=maxi;
	            if(i==j) arr[i][j]=0;
	        }	    
	    for(int i=0;i<edge;i++){
	        str = br.readLine();
	        st = new StringTokenizer(str);
	        int a = Integer.parseInt(st.nextToken());
	        int b = Integer.parseInt(st.nextToken());
	        int val = Integer.parseInt(st.nextToken());
	        arr[a][b]=0;
	        if(val==0) arr[b][a]=1;
	        else arr[b][a]=0;
	    }       
	    for(int k=1;k<=node;k++)
	        for(int i=1;i<=node;i++)
	            for(int j=1;j<=node;j++)
	                if(arr[i][j] > arr[i][k] + arr[k][j])
	                    arr[i][j] = arr[i][k] + arr[k][j];
	    
	    str = br.readLine();
	    st = new StringTokenizer(str);
	    query = Integer.parseInt(st.nextToken());	        
	    for(int i=0;i<query;i++){
	        str = br.readLine();
	        st = new StringTokenizer(str);
	        int a = Integer.parseInt(st.nextToken());
	        int b = Integer.parseInt(st.nextToken());
	        System.out.println(arr[a][b]);
	    }
	}
}