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

13 Aug 2023 in Algorithm on 그래프 이론

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

풀이

일방통행인 길을 양방향으로 바꿔 목적지로 갈 수 있도록 해야한다.

플로이드-워셜 알고리즘을 사용하는데 일방통행인 길은 양방향으로 바꿔줘야하므로 1이라는 가중치를 두고, 양방향길은 0으로 저장한다.

플로이드-워셜 알고리즘으로 u에서 v로 가는데 바꿔야 할 길의 수를 구해놓고

질문이 올 때마다 저장된 배열에서 값을 출력한다.

---

메모리: 31772KB

시간: 440ms

언어: Java 11

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] dist = new int[n + 1][n + 1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (i != j) {
                    dist[i][j] = 100000000;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            dist[u][v] = 0;
            dist[v][u] = b == 0 ? 1 : 0;
        }

        for (int k = 1; k < n + 1; k++) {
            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < n + 1; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        int k = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            sb.append(dist[s][e]).append("\n");
        }

        System.out.println(sb);
    }

}