백준 1613 : 역사

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

얼핏보면 위상정렬 문제같다. 선후관계가 명확하고 그래프가 DAG이기 때문이다.

그러나 아예 연결이 안되어 있는 그래프

즉 선후관계가 정해져 있지 않은 그래프를 처리하는게 Topological Sort 로는 애매해보였다.

선후관계를 단방향 그래프로 생각했을 때 전체 그래프의 연결여부를 확인 할 수 있는게 또 하나 있다.

바로, 플로이드-와샬 알고리즘, n=400 이라 충분히 n^3 이 가능해서 생각해보았다.

플로이드 와샬을 썼을때 2차원배열에서

i->j로 갈때 INF가 떴다는 것은 i 에서 j 로 갈 수 없다는 것이다.

이때, 만약 j->i 가 INF가 아니라 다른 숫자라면 j->i로는 갈 수 있고 따라서 j 가 i 보다 먼저 일어난 선후관계를 알 수 있다.

반대도 마찬가지.

또 i->j 경로와 j->i 경로가 모두 INF 가 뜰경우 서로 아예 연결이 안되어있다는 얘기이므로 선후관계를 정립할 수 없다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#include <iostream> #define MAX 401 #define INF 1000000000 using namespace std; int matrix[MAX][MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ matrix[i][j] = (i==j) ? 0:INF; } } while(m--){ int a, b; cin >> a >> b; matrix[a][b] = 1; } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(matrix[i][j] > matrix[i][k] + matrix[k][j]){ matrix[i][j] = matrix[i][k] + matrix[k][j]; } } } } int t; cin >> t; while(t--){ int a, b; cin >> a >> b; if(matrix[a][b] != INF && matrix[b][a] == INF){ cout << -1 << '\n'; }else if(matrix[b][a] != INF && matrix[a][b] == INF){ cout << 1 << '\n'; }else{ cout << 0 << '\n'; } } return 0; }