[ 백준 ] 1613번 - 역사 (C++)

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

1613번: 역사

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/24

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

 

1. arr[ n ][ n ] 배열을 만들어서 각 사건별로 전후 관계를 저장합니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 나머지 사건들의 전후 관계를 갱신해 줍니다.

 

3. 입력받은 사건들의 전후 관계를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
 
using namespace std;
 
int n, k, s;
int arr[401][401];
 
int main()
{
    scanf("%d %d ", &n, &k);
 
    for (int i = 0; i < k; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        arr[a][b] = -1;
        arr[b][a] = 1;
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[j][i] == 0) continue;
 
            for (int k = 1; k <= n; k++) {
                if (arr[j][i] == arr[i][k]) {
                    arr[j][k] = arr[j][i];
                }
            }
        }
    }
 
    scanf("%d", &s);
 
    for (int i = 0; i < s; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", arr[a][b]);
    }
}