[C++] 백준 1613 : 역사

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

1613번: 역사

백준 1613번 역사 문제를 풀었다.

 

플로이드 와샬 알고리즘을 응용해서 푸는 문제다.

예제를 입력받고 플로이드 와샬 알고리즘을 수행한 후의 dist배열을 살펴보자.

dist	1	2	3	4	5
1	0	1	1	2	INF
2	INF	0	1	1	INF
3	INF	INF	0	1	INF
4	INF	INF	INF	0	INF
5	INF	INF	INF	INF	0

dist[i][j]의 값이 INF가 아니라는 것은 i 노드에서 j 노드로 가는 경로가 있다는 것이다.

이것을 문제에 적용시켜보면 i 번 사건이 j 번 사건보다 먼저 일어났다는 것이다.

 

dist[i][j]의 값이 INF라면 두 가지 경우를 생각해야한다.

dist[j][i]의 값도 INF인 경우와 INF가 아닌 경우다.

dist[j][i]의 값도 INF라면 두 사건은 어느 사건이 먼저 일어났는지 모르는 것이다.

dist[j][i]의 값이 INF가 아니라면 j 번 사건이 i 번 사건보다 먼저 일어났다는 것이다.

 

이것을 토대로 조건문을 작성해주면 된다.

 

아래는 전체 코드입니다.

#pragma warning(disable:4996)
#include <iostream>
#include <string>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 100000

int adj[401][401];
int dist[401][401];

int main() {
	int n, k;
	cin >> n >> k;

	int a, b;
	for (int i = 0; i < k; i++) {
		scanf("%d %d", &a, &b);
		adj[a][b] = 1;
	}

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

	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;
	while (s--) {
		scanf("%d %d", &a, &b);
		if (dist[a][b] == INF) {
			if (dist[b][a] == INF)
				printf("0\n");
			else
				printf("1\n");
		}
		else
			printf("-1\n");
	}

	return 0;
}