[BaekJoon] 1613 역사 (Java)

1.  문제 링크

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

2.  문제

요약

• 세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계를 알 수 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 400보다 작거나 같은 자연수인 사건의 개수 n과 50,000보다 작거나 같은 자연수인 사건의 전후 관계의 개수 k가 주어지고 두 번째 줄부터 k개의 줄에 전후 관계를 알고 있는 두 사건의 번호가 주어집니다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미합니다. k + 2번째 줄에는 50,000보다 작거나 같은 자연수인 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s가 주어지고 다음 줄부터 s개의 줄에는 서로 다른 두 사건의 번호가 주어집니다.
  • 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수입니다.
• 출력: s개의 줄에 걸쳐 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 유추할 수 없다면 0을 출력합니다.

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static final int MAX = Integer.MAX_VALUE;
    static int n, k, s;
    static int[][] distances, question;
    static void input() {
        Reader scanner = new Reader();
        n = scanner.nextInt();
        k = scanner.nextInt();
        distances = new int[n + 1][n + 1];
        for(int event = 1; event <= n; event++) {
            for(int event2 = 1; event2 <= n; event2++) {
                if(event != event2) distances[event][event2] = MAX;
            }
        }
        for(int idx = 0; idx < k; idx++) {
            int before = scanner.nextInt(), next = scanner.nextInt();
            distances[before][next] = 1;
        }
        s = scanner.nextInt();
        question = new int[s][2];
        for(int idx = 0; idx < s; idx++) {
            question[idx][0] = scanner.nextInt();
            question[idx][1] = scanner.nextInt();
        }
    }

    static void solution() {
        floydWarshall(distances);
        for(int idx = 0; idx < s; idx++) {
            int first = question[idx][0], second = question[idx][1];
            if(distances[first][second] != MAX && distances[second][first] == MAX) {
                sb.append(-1).append('\n');
            } else if(distances[first][second] == MAX && distances[second][first] != MAX) {
                sb.append(1).append('\n');
            } else if(distances[first][second] == MAX && distances[second][first] == MAX) {
                sb.append(0).append('\n');
            }
        }
        System.out.println(sb);
    }

    static void floydWarshall(int[][] distances) {
        for(int middle = 1; middle <= n; middle++) {
            for(int start = 1; start <= n; start++) {
                for(int end = 1; end <= n; end++) {
                    if(start == end) continue;
                    if(distances[start][middle] == MAX || distances[middle][end] == MAX)
                        continue;
                    if(distances[start][end] > distances[start][middle] + distances[middle][end])
                        distances[start][end] = distances[start][middle] + distances[middle][end];
                }
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 주어진 사건들의 전후 관계를 표현하기 위해 2차원 배열 distances를 생성하고 열과 행의 수가 같은 위치만 0으로 나머지 위치는 INF로 초기화합니다.
• 주어진 사건들의 전후 관계에서 먼저 일어난 사건을 before, 이후에 일어난 사건을 next라고 한다면 distances[before][next] = 1 로 하여 사건들의 전후 관계를 표시합니다.
• distances 배열을 이용하여 Floyd Warshall 알고리즘을 통해 모든 각 사건들에서 다른 모든 사건들로의 최단 거리를 구합니다.
• 이렇게 구한 distances 배열에 있는 값은 아래와 같은 뜻을 나타냅니다.
  • distances[a][b] == INF : 사건 a가 사건 b보다 늦게 일어났다.
  • distances[a][b] != INF : 사건 a가 사건 b보다 먼저 일어났다.
• 전후 관계를 알고 싶은 사건 쌍들에 대해 아래와 같은 사항을 확인합니다. 편의상 앞에 있는 번호의 사건을 a, 뒤에 있는 번호의 사건을 b라고 하겠습니다.
  • distances[a][b] != INF && distances[b][a] == INF : 두 개의 조건에서 앞의 조건은 a는 b보다 먼저 일어났다는 뜻이 되고 뒤의 조건은 b가 a보다 늦게 일어났다는 뜻이 되니 결국 사건 a가 사건 b보다 먼저 일어났다는 뜻이 됩니다.
  • distances[a][b] == INF && distances[b][a] != INF : 두 개의 조건에서 앞의 조건은 a가 b보다 늦게 일어났다는 뜻이 되고 뒤의 조건은 b가 a보다 일찍 일어났다는 뜻이 되므로 결국 사건 b가 사건 a보다 먼저 일어났다는 뜻이 됩니다.
  • distances[a][b] == INF && distances[b][a] == INF : 두 개의 조건에서 앞의 조건은 a가 b보다 늦게 일어났다는 뜻이 되고 뒤의 조건은 b가 a보다 늦게 일어났다는 뜻이 되므로 결국 두 사건의 전후 관계를 예측할 수 없다는 뜻이 됩니다.
• 위 3개의 조건을 확인하여 각 사건 쌍의 전후 관계를 파악합니다.