[백준] 1613번. 역사

[백준] 1613번. 역사

1. 문제

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

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

2. 입력

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

3. 출력

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

4. 풀이

• 앞서 푼 플로이드 와샬 문제 코드를 그대로 이용했다.
• INF와 출력만 수정했다.
• 역사를 알 수 없는 경우 0을 출력하기 때문에 INF 대신 0을 입력하였다.

5. 처음 코드와 달라진 점

• 출력을 편하게 하기 위해 INF를 0으로 사용했는데 조건식을 INF로 그대로 둬서 수정했다.

6. 코드

#include <iostream>
#include <algorithm>
#define INF 1e9
using namespace std;

int graph[401][401];

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int number_of_events, number_of_operation;
	cin >> number_of_events>>number_of_operation;

	for (int i = 1; i <= number_of_events; i++){
		for (int j = 1; j <= number_of_events; j++) {
			graph[i][j] = 0;
		}
	}

	for (int i = 0; i < number_of_operation; i++){
		int past, future;
		cin >> past >> future;
		graph[past][future] = -1;
		graph[future][past] = 1;
	}

	for (int k = 1; k <= number_of_events; k++){
		for (int i = 1; i <= number_of_events; i++) {
			for (int j = 1; j <= number_of_events; j++) {
				if (graph[i][j] == 0) {
					if (graph[i][k] == -1 && graph[k][j] == -1) graph[i][j] = -1;
					if (graph[i][k] == 1 && graph[k][j] == 1) graph[i][j] = 1;
				}
			}
		}
	}

	int number_of_events_want_to_know;
	cin >> number_of_events_want_to_know;

	for (int i = 0; i < number_of_events_want_to_know; i++){
		int first_event, second_event;
		cin >> first_event >> second_event;
		cout<<graph[first_event][second_event]<<"\n";
	}
}