백준 1613 - 역사

문제

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

리뷰

플로이드 워셜로 풀이할 수 있는 간단한 문제였다.

주어지는 사건의 전후 관계를 전 $\rightarrow$ 후 방향의 형태로 그래프를
형성해준다. 이후, 플로이드 워셜을 돌리며 모든 사건(정점)간의 관계를 도출한다.

$s$개의 쿼리를 처리할 때 $i, j$가 주어지면, map[i][j]가 MAX_VALUE 가
아닐 때는 $i \rightarrow j$인 경우로 -1이 답이 되고, map[j][i]가 MAX_VALUE가
아닐 때는 $j \rightarrow i$인 경우로 1이 답이 된다. 이외 경우는 관계를 유추할 수 없으므로
0으로 처리해주면 된다.

로직의 시간복잡도는 플로이드 워셜의 $O(N^3)$으로 수렴하고, $N=400$인 최악의
경우에도 무난히 제한 조건 1초를 통과한다.

코드

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

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

public class Main {
    static int N;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = parseInt(st.nextToken());
        int K = 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) continue;

                map[i][j] = MAX_VALUE;
            }

        int u, v;
        while (K-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());

            map[u][v] = 1;
        }

        floyd();

        int s = parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (s-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());

            if (map[u][v] != MAX_VALUE) {
                sb.append("-1");
            } else if (map[v][u] != MAX_VALUE) {
                sb.append("1");
            } else {
                sb.append("0");
            }

            sb.append("\n");
        }

        System.out.print(sb);
        br.close();
    }

    static void floyd() {
        for (int k = 1; k <= N; k++)
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++) {
                    if (map[i][k] == MAX_VALUE || map[k][j] == MAX_VALUE) continue;

                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
    }
}

결과