백준 1613 역사

 

이 문제는 각역사간 관계가 주어졌을때 각 사건들의 관계를 파악하는 문제입니다.

 

각 사건들의 전후관계를 알기 위해서는 결국 이 두사건이 한사건에서 다른사건으로 도달 할 수 있느냐를 알면 됩니다.

 

따라서 주어진 사건의 관계들을 단방향 그래프로 생각하여 사건노드에서 다른사건노드로 가는 경로의 존재유무를 알면 문제를 해결 할 수 있습니다.

 

N이 400이하이므로 플로이드 와샬 알고리즘을 이용하면 모든 사건에 대한 경로를 파악할 수 있습니다.

 

이때 a,b가 순서대로 주어진다면 dp[a][b] 의 값이 존재하면 a가 더 빨리 발생한 사건이고 dp[b][a]값이 존재한다면 b가 더 빨리 발생한 사건이고 둘다 존재하지 않는다면 둘은 서로 관련이 없음을 알 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

#define INF 987654321
using namespace std;

int dp[500][500];

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


	int n, k; cin >> n >> k;
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] = INF;


	for (int i = 0; i < k; i++) {
		int a, b; cin >> a >> b;
		dp[a][b] = 1;
	}

	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}


	int s; cin >> s;

	for (int i = 0; i < s; i++) {
		int a, b; cin >> a >> b;		
		if (dp[a][b] == INF && dp[b][a] == INF) cout << 0 << '\n';
		else if (dp[a][b] == INF && dp[b][a] != INF) cout << 1 << '\n';
		else cout << -1 << '\n';

	}


	return 0;
}