[백준] 1613: 역사 - JAVA

in Algorithm on 그래프 이론

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

풀이

사건들의 전후관계를 확인하는 문제이다.

이차원배열을 만들어 a사건 이후에 b사건이 이루어진다면 arr[a][b]를 true로 저장했다.

이때 플로이드-워셜 알고리즘을 사용했다.

for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (table[i][k] && table[k][j]) {
                table[i][j] = true;
            }
        }
    }
}

배열을 다 채운 후 입력을 받으면서 table[a][b]가 true이면 -1, table[b][a]가 true이면 1, 둘 다 false이면 0을 출력했다.

메모리: 38252KB

시간: 472ms

언어: 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 K = Integer.parseInt(st.nextToken());

        boolean[][] table = new boolean[N + 1][N + 1];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            table[a][b] = true;
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                if (!table[i][k]) {
                    continue;
                }
                for (int j = 1; j <= N; j++) {
                    if (table[k][j]) {
                        table[i][j] = true;
                    }
                }
            }
        }

        int S = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < S; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            boolean foward = table[a][b];
            boolean reverse = table[b][a];

            if (foward && !reverse) {
                sb.append("-1");
            } else if (!foward && reverse) {
                sb.append("1");
            } else {
                sb.append("0");
            }

            sb.append("\n");
        }

        System.out.println(sb);
    }

}