[BOJ] 백준 1613 : 역사 (java)

🧪 1613 역사

---

난이도 : 🌟 골드 3
유형 : 플로이드 워셜 알고리즘

1613번: 역사

 

📝 문제

---

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

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

 

입력

 

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

 

출력

 

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

 

🧐 핵심 로직

---

1. 노드 a에서 노드 b로 간선이 존재하면 prob[a][b]를 -1로, prob[b][a]를 1로 저장한다.
2. 바로 이어지는 간선은 없지만 다른 노드를 거쳐서 이어지는 경우를 처리하기 위해 prob[i][j]가 0이고, prob[i][k] + prob[k][j]가 -2이면 prob[i][j]를 -1로, 2이면 1로 설정한다.
3. 추가로 입력을 받아서 노드 쌍 간의 관계를 출력한다.

💻 최종 코드 (1176 ms)

---

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

public class Main {
    static int n, m, a, b, s;
	static int[][] prob;

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

		prob = new int[n+1][n+1];
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < n+1; j++) {
				prob[i][j] = 0;
			}
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			prob[a][b] = -1;
			prob[b][a] = 1;
		}

		for (int k = 1; k < n+1; k++) {
			for (int i = 1; i < n+1; i++) {
				for (int j = 1; j < n+1; j++) {
					if (prob[i][j] == 0) {
						if (prob[i][k] + prob[k][j] == -2) {
							prob[i][j] = -1;
						}
						else if (prob[i][k] + prob[k][j] == 2) {
							prob[i][j] = 1;
						}
					}
				}
			}
		}

		s = Integer.parseInt(br.readLine());
		for (int i = 0; i < s; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			System.out.println(prob[a][b]);
		}
    }
}