백준 BOJ 1613 - 역사

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

1613번: 역사

바로 앞서 풀었던 문제와 동일한 유형

앞선 문제에서 태그를 까봤더니 플로이드-와샬이더라...

arr[a][b] 를 a가 b 앞에 오는 사건인지 체크하는 용도로 사용한다.

 

플로이드 와셜을 통해서 모든 a,b 쌍들에 대해서

사건 간의 전후관계를 설정해 주고,

 

정답을 출력할 때

arr[a][b] 가 true라면 앞서는 것이고,

arr[b][a] 가 true라면 뒤에 오는 사건인 것이고,

둘 다 아니라면 서로 연관이 없는 별개의 사건인 것이다.

 

각각의 조건에 맞게 출력해주면 된다.

입출력 쿼리의 갯수가 꽤나 많아서 TLE를 한번 받았다.

fastio를 해주도록 하자.

 

확실히 DFS 풀이보다 이게 훨씬 깔끔한듯 싶다.

플로이드 와샬은 다익스트라 N번 돌리는게 더 빠르지 않나 싶어서

기억의 저편에 밀어뒀는데

이렇게 써먹을 수도 있구나 하고 새로 깨달음.

#include <bits/stdc++.h>
using namespace std;

bool arr[456][456] = {0};

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N,K;
	int a,b;
	cin >> N >> K;
	for(int i=0; i<K; i++){
		cin >> 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(arr[i][k] && arr[k][j]) arr[i][j] = true;
			}
		}
	}
	
	int Q;
	cin >> Q;
	while(Q--){
		cin >> a >> b;
		if(arr[a][b]) 		cout << "-1\n";
		else if(arr[b][a]) 	cout << "1\n";
		else 				cout << "0\n";
	}
	return 0;
}