[백준] 역사 (1613번)

문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

---

bfs로 해결이 가능할 것 같아 bfs로 풀었으나 시간초과가 떴다.

플로이드-와샬 알고리즘을 쓰면 간단하게 풀 수 있는 문제였다.

for (int k = 1; k <= N; k++)         // 중간점
{
    for (int i = 1; i <= N; i++)    // 시작점
    {
        for (int j = 1; j <= N; j++) // 도착점
        {
            if(시작점과 도착점의 관계를 알고싶으면)
            {
                if(시작점 > 중간점 && 중간점 > 도착점) 시작점 > 도착점
                else if(시작점 < 중간점 && 중간점 < 도착점) 시작점 < 도착점
            }
        }
    }
}

플로이드 와샬의 일반적인 방법이다.

이를 이용해 이 문제에 적용한다.

a가 b보다 먼저일어났고 b가 c보다 먼저 일어났다면 a는 c보다 먼저일어났으므로 저 식에 대입하기 좋아보인다.

if (p[i][k] == 1 && p[k][j] == 1) p[i][j] = 1; 가 바로 이를 구현한 식이다.

그 외에 큰 어려움은 없다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%97%AD%EC%82%AC%20(1613).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n, k, s;
int p[401][401];
void floyd()
{
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (p[i][j] == 0) {
					if (p[i][k] == 1 && p[k][j] == 1)
						p[i][j] = 1;
					if (p[i][k] == -1 && p[k][j] == -1)
						p[i][j] = -1;
				}
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;
	for (int a, b, i = 0; i < k; i++) {
		cin >> a >> b;
		p[a][b] = -1;
		p[b][a] = 1;
	}

	floyd();

	cin >> s;
	for (int a, b, i = 0; i < s; i++) {
		cin >> a >> b;
		cout << p[a][b] << "\n";
	}
}