[Floyd] 1613번 역사

1613번 역사

 

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

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

5 5
1 2
1 3
2 3
3 4
2 4
3
1 5
2 4
3 1

 

예제 출력

0
-1
1

 

해결방법

모든 정점간의 연결 유무를 파알하는 All-to-All 문제이다

 

n≦400 이고, 알고싶은 연결 여부는 50,000개 이하이다

따라서 다익스트라 m번 vs 플로이드-와샬 에서 플로이드 알고리즘을 선택할 수 있다

 

간선의 정보가 1 2 로 입력된다면 이는 1사건이 2사건보다 먼저 일어났다는 뜻이다

따라서 conn[1][2] 의 값이 설정되었다면 논리적으로 conn[2][1] 는 값이 들어갈 수 없다

 

이러한 개념으로 모든 정점간의 연결 유무를 conn[][] 에 설정을 해준다

 

알고싶은 정점간의 관계를 입력받은 후에

• 둘 다 설정되어있지 않으면 0 출력
• [u][v] 라면 -1 출력
• [v][u] 라면 1 출력

for(int i=0; i<m; i++){
    cin >> u >> v;
    
    if(!conn[u][v] && !conn[v][u]) cout << 0 << "\n";
    else if(conn[u][v]) cout << -1 << "\n";
    else if(conn[v][u]) cout << 1 << "\n";
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 401
#define INF 987654321
using namespace std;

int n,m;
int u,v;

int adj[MAX][MAX];
bool conn[MAX][MAX];

void floyd(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j) conn[i][j] = true;
            else if(adj[i][j] > 0) conn[i][j] = true;
            else conn[i][j] = false;
        }
    }
    
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==k || j==k) continue;
                if(i==j) continue;
                
                if(!conn[i][j]){
                    if(conn[i][k] && conn[k][j]){
                        conn[i][j] = true;
                    }
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<m; i++){
        cin >> u >> v;
        adj[u][v] = 1;
    }
    
    floyd();
    
    cin >> m;
    
    for(int i=0; i<m; i++){
        cin >> u >> v;
        
        if(!conn[u][v] && !conn[v][u]) cout << 0 << "\n";
        else if(conn[u][v]) cout << -1 << "\n";
        else if(conn[v][u]) cout << 1 << "\n";
    }
}