백준 1613 역사

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

1613번: 역사

처음에는 먼저 일어난 사건을 부모, 나중에 일어난 사건을 자식으로 생각하고 그래프 그려서 dfs나 bfs 써도 널널할 거 같았지만 중복 탐색이 많아 플로이드 워셜을 이용해 풀었습니다.

 

플로이드 워셜은 원래 모든 점에서 모든 점으로의 최단, 최대 경로를 찾는 것이지만, 이를 응용하여 경로 유무만 파악합니다. O(n^3) 이지만 n <= 400 이므로 널널합니다. 

 

graph[i][j] 를 i -> j 로 가는 경로가 존재할 때 true, 아니면 false로 잡고 플로이드 워셜의 graph[i][k] & graph[k][j] 를 이용해 true가 나오면 i -> j 로 가는 경로가 존재하는 것입니다. (이 때 j가 먼저 일어난 사건이라 가정)

 

다만 추후 탐색에서 false인 graph[k][j]가 발생할 수 있으므로 true로 계산되면 뒤는 계산하지 않습니다.

 

코드는 다음과 같습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, k, s;

bool graph[401][401]; // [i][j] : i -> j 존재하면 true (j가 먼저 일어난 사건)

void init()
{
    cin >> n >> k;
    memset(graph, sizeof(graph), false);

    int before, after;    
    for(int i = 0; i < k; i++) {
        cin >> before >> after;
        graph[after][before] = true;
    }
}

void calc()
{
    // 플로이드 와샬 응용
    // 경로 유무만 파악하면 되므로 and로 계산
    // i -> k true and k -> j true => i -> j true
    // n <= 400 이므로 n^3 가능 
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(graph[i][j] == true)
                    continue;
                graph[i][j] = graph[i][k] & graph[k][j];
            }
        }
    }
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    calc();
    
    cin >> s;
    int a, b;
    for(int i = 0; i < s; i++) {
        cin >> a >> b;
        if(graph[a][b] == false && graph[b][a] == false) {
            // 경로 없는 경우
            cout << 0 << '\n';
        }
        else if(graph[a][b] == false && graph[b][a] == true) {
            // a가 먼저 일어난 사건인 경우
            cout << -1 << '\n';
        }
        else if(graph[a][b] == true && graph[b][a] == false) {
            // b가 먼저 일어난 사건인 경우
            cout << 1 << '\n';
        }
        else {
            // 모순 없음
            continue;
        }
    }
}