[백준] 1613번: 역사

📌 문제

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

📌 설명

 주어진 두 수의 전후 관계를 판별하는 문제이다. 대충 문제를 보고 위상정렬이겠거니 하고 풀었지만 WA가 나왔다. 위상정렬 풀이의 반례는 비연결 그래프 상황이다. 1->3, 2->4에서 3, 4의 전후 관계는 판별할 수 없다. 그렇다면 Union-Find를 추가로 사용하면 어떨까? 이 방법도 반례가 존재한다. 1->2, 1->3에서 2, 3의 전후 관계는 판별할 수 없다. 그렇다면 어떤 알고리즘을 사용해야 하는가? 이 문제는 최단 경로 문제이며, 플로이드-워셜 알고리즘을 통해 모든 노드 간 최단 거리를 통해 풀어야 한다. 두 노드 a, b가 있을 때, dist[a][b] != INF라면, a에서 b로 향하는 경로가 존재한다는 것이고, a 사건이 먼저 일어난 것이다. (dist: 최단 거리 배열) 모든 노드간 가중치를 1로 설정한다.

 DFS, BFS로 풀 수 있다고 하나, 더 직관적인 방법은 플로이드-워셜이라고 생각한다.

📌 코드

#include <iostream>
#include <algorithm>

#define INF 401

using namespace std;

int dist[401][401];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dist[i][j] = 0;
			else
				dist[i][j] = INF;
		}
	}

	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b; // a 다음에 b 발생
		dist[a][b] = 1;
	}

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

	int s;
	cin >> s;
	for (int i = 0; i < s; i++) {
		int a, b;
		cin >> a >> b;

		if (dist[b][a] != INF)
			cout << "1\n";
		else if (dist[a][b] != INF)
			cout << "-1\n";
		else
			cout << "0\n";
	}
}