[백준 1613] 역사 C++

1613번: 역사

플로이드-와샬

---

1. 문제 해결 아이디어

 

사건들의 전후 관계를 파악하는 문제라서 처음에 바로 위상 정렬로 풀기 시작했었다.

근데 위상 정렬을 해놓으니 관계도는 명확히 그려지지만 임의의 정점 2개를 선택했을 때 해당 정점들이 서로 어떤 관계에 있는지 알아보려면 매번 BFS가 필요해 보였다. 효율이 안 좋게 느껴졌고 위상 정렬은 아닌 것 같아 알고리즘 분류를 켜서 어떤 알고리즘을 써야 하는지 힌트를 받았다.

 

플로이드-와샬 알고리즘을 쓰는 문제였다.

N이 400으로 매우 작고, 문제를 다시 읽어보니 단방향 그래프 이기 때문에 A라는 정점에서 B라는 정점으로 갈 수만 있다면 A는 B보다 먼저 일어난 일임을 자명하게 알 수 있었다.

 

그래서 플로이드 알고리즘을 통해 A에서 B로가는 방법이 있는지를 확인하는 배열을 만들었다.

 

A에서 B로 갈 수 있다면 A사건이 B보다 먼저 일어났다는 뜻이고, B에서 A로 갈 수 있다면 B사건이 A보다 먼저 일어났다는 뜻이다.

만약 둘 다 없다면 유추할 수 없는 사건이다.

 

문제에서 전후 관계가 모순인 경우는 없다고 했기 때문에 플로이드 배열을 만들면 A와 B배열의 전후 관계를 찾는 건 간단했다.

---

2. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, K, S;
vector<int> Graph[401];
int order[401][401];
pii ires[50001];
 
void input(){
    cin >> N >> K;
    int a, b;
    for(int i = 0; i < K; i++){
        cin >> a >> b;
        Graph[a].push_back(b);
        order[a][b] = 1;
    }
    
    cin >> S;
    for(int i = 0; i < S; i++){
        cin >> a >> b;
        ires[i] = {a, b};
    }
}
 
void Folyd(){
    for(int k = 1; k <= N; k++){
        for(int r = 1; r <= N; r++){
            for(int c = 1; c <= N; c++){
                if(order[r][k] && order[k][c]){
                    order[r][c] = 1;
                }
            }
        }
    }
    for(int i = 0; i < S; i++){
        int now = order[ires[i].first][ires[i].second];
        int rev_now = order[ires[i].second][ires[i].first];
        if(now) cout << -now << "\n";
        else if(rev_now) cout << rev_now << "\n";
        else cout << 0 << "\n";
    }
}
 
int main(){
    fasti
    input();
    Folyd();
    
    return 0;
}