[ BOJ ][JAVA][1613] 역사

www.acmicpc.net/problem/1613

1613번: 역사

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	10053	3366	2350	33.141%

문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

예제 입력 1

5 5
1 2
1 3
2 3
3 4
2 4
3
1 5
2 4
3 1

예제 출력 1

0
-1
1

코드

/*
    플로이드 와샬 알고리즘 적용
*/
import java.io.*;
import java.util.*;

public class p1613 {
    static int n, k, s;
    static int[][] dist;
    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()); // 사건의 수

        dist = new int[n + 1][n + 1];

        k = Integer.parseInt(st.nextToken()); // 사건 관계의 수
        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            dist[u][v] = -1;
            dist[v][u] = 1;
        }

        folyd_warshall();

        s = Integer.parseInt(br.readLine()); // 알고 싶은 사건 쌍의 수
        while (s-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            System.out.println(dist[u][v]);
        }
    }

    static void folyd_warshall() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][j] == 0) {
                        if (dist[i][k] == 1 && dist[k][j] == 1) {
                            dist[i][j] = 1;
                        } else if (dist[i][k] == -1  && dist[k][j] == - 1) {
                            dist[i][j] = -1;
                        }
                    }
                }
            }
        }
    }
}