백준 #1613 역사


BOJ #1613 - 역사

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

# 문제 분류

최단 경로 찾기 (Floyd-Warshall Algorithm)

풀이 접근 방법


  1. 각 노드쌍에 대한 최단 경로를 모두 구해야 하므로 역시 Floyd-Warshall 알고리즘을 사용하면 된다.
  2. INF와 0으로 각각 초기화 한 후, dist[i][j]가 INF, 즉 갱신되지 않았다면 선후관계가 성립하지 않는다.
  3. 즉, dist[i][j] != INF이면 i → j, dist[j][i] != INF이면 j → i, 둘 다 INF라면 선후관계를 파악할 수 없는 케이스이다.

얍.

소스 코드


#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int INF = 1e9;
int n, k, a, b, s;
int arr[410][410];

int main(){
    for(int i=0; i<410; i++){
        for(int j=0; j<410; j++){
            arr[i][j] = INF;
            arr[j][j] = 0;
        }
    }

    scanf("%d %d", &n, &k);
    for(int i=0; i<k; i++) {
        scanf("%d %d", &a, &b);
        arr[a][b] = 1;
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=1; k<=n; k++){
                arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
            }
        }
    }

    scanf("%d", &s);
    for(int i=0; i<s; i++){
        scanf("%d %d", &a, &b);
        if(arr[a][b] != INF) printf("-1\n");
        else if(arr[b][a] != INF) printf("1\n");
        else printf("0\n");
    }

    return 0;
}