BOJ 1613 - 역사

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

이전 풀이: http://joonas-yoon.blogspot.com/2016/04/1613.html

문제

알고 있는 사건의 전후 관계를 방향성이 있는 간선으로 보면, 서로 다른 두 사건을 유추한다는 것은 어떤 방향으로건 일단 연결이 되어있는가를 물어보는 것이다.

방향 그래프에서 정점 a에서 b로 갈 수 있는 경로가 있는 지 물어보는 문제이다.

a에서 b로 가는 경로가 있으면 앞에 있는 사건이 먼저 일어난 것이므로 -1

b에서 a로 가는 경로가 있다면 1, 경로가 없다면 0을 출력하면 된다.

문제는 이러한 물음이 한두번이 아니라 s번(최대 50,000번) 물어보기 때문에, 경로를 빠르게 찾을 수 있어야한다. 

n이 400으로 작으므로 플로이드 와샬로 각 사건의 연결 관계를 모두 구해둔다면, 쿼리의 대답이 O(1)이므로 시간 내에 해결 가능하다.

코드

	#include <cstdio>
	int main() {
	int n, K;
	scanf("%d %d", &n, &K);
	bool g[401][401] = {};
	while (K--) {
	int s, e;
	scanf("%d %d", &s, &e);
	g[s - 1][e - 1] = true;
	}
	for (int k = 0; k < n; ++k) {
	for (int i = 0; i < n; ++i) {
	if (!g[i][k]) continue;
	for (int j = 0; j < n; ++j) {
	g[i][j] |= g[i][k] & g[k][j];
	}
	}
	}
	int q;
	scanf("%d", &q);
	while (q--) {
	int s, e;
	scanf("%d %d", &s, &e);
	if (g[s - 1][e - 1])
	puts("-1");
	else if (g[e - 1][s - 1])
	puts("1");
	else
	puts("0");
	}
	return 0;
	}

view raw boj-1613.cpp hosted with ❤ by GitHub