[백준 알고리즘] 1613번: 역사

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

문제

문제

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

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

입력

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

출력

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

풀이

플로이드 와셜 알고리즘으로 해결했다. 이번에는 전후관계를 기록해야하기 때문에, 앞선 사건은 -1, 이후 사건은 1, 관계성이 없으면 0으로 설정했다. 만약 i에서 어떤 지점 k를 거쳐서 j에 도달하는 경로 d[i][k]== -1 && d[k][j] == -1 가 존재한다면 i 는 j 보다 앞선 사건임이 맹배하고, 반대로 j는 i 보다 느린 사건임이 확인된다. 따라서 플로이드 와셜 알고리즘으로 먼저 앞선 사건들의 관계를 모두 찾고, 앞선 관계들은 역으로 느린 관계들에 대한 표시를 해주는 것으로 해결할 수 있었다.

코드

#include <iostream>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

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

    for (int m = 1; m <= n; m++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][m] == -1 && dist[m][j] == -1) dist[i][j] = -1;
            }
        }
    }

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

    int s;
    cin >> s;
    while (s--) {
        int a, b;
        cin >> a >> b;
        cout << dist[a][b] << "\n";
    }

}