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

문제링크

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

11562번: 백양로 브레이크

 

• 양방향의 경우 u->v로 가는 길은 무조건 존재한다.  -->비용이 없다고 생각하고 0으로 표시
• 단방향의 경우 v->u로 연결된 길이 없다 -> 가는데 1의 비용이 발생한다고 생각 (가는데 연결해야 되는 단방향의 경우의 수를 구하면 됨으로)
• floyd 알고리즘 적용

package BOJ;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_11562 {
    static int n,m;
    static int map[][];
    static int INF = 999999999;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken()); //건물의 수
        m = Integer.parseInt(st.nextToken()); // 길의 수
        map = new int[n+1][n+1];

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i!=j) map[i][j] = INF;
            }
        }

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()); //
            int v = Integer.parseInt(st.nextToken()); //u-v로 가는 길길
            int b = Integer.parseInt(st.nextToken()); //0:일반통행 1:양방향
            if(b == 0){//단방향
                map[u][v] = 0;
                map[v][u] = 1; //단방향의 경우 v-u로 갈때는 비용발생
            }else{
                map[u][v] = 0;
                map[v][u] = 0;
            }
        }

        for(int k=1;k<=n;++k){
            for(int i=1;i<=n;++i){
                for(int j=1;j<=n;++j){
                    if(i ==j) continue;
                    map[i][j] = Math.min(map[i][j],map[i][k]+map[k][j]);
                }
            }
        } //플로이드 적용해서 가는 비용 구하기

        //for(int i=1;i<=n;i++) System.out.println(Arrays.toString(map[i]));
        int k = Integer.parseInt(br.readLine()); //학생들의 질문의 수
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0;i<k;i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

           bw.write(map[s][e]+"\n");
        }
        bw.flush();
        bw.close();
    }

}