[백준] 1613번 : 역사

1613번: 역사

---

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

이 문제를 풀기위해 플로이드 와샬 알고리즘을 공부했다. 이 문제를 DFS만으로 풀려고 하니까 TC에서 헤어나오질 못하였다. 사실 당연하다. 최대 정점의 수는 500개이나, 이후 최대 50,000개의 사건이 주어지므로, DFS 1번 당 최대 50,000 재귀를 한다고 할 때, 25,000,000번 호출되지 않을까? 하는 생각이 들었다. 역시 어떻게 풀어야할지 몰라 무식하게 접근한 꼴이다.

 

플로이드 와샬을 이용해 모든 정점에서의 다른 정점으로 가는 최단 경로를 구하여, 주어지는 사건 쌍(v1, v2)가 있으면, distance[v1][v2]와 distance[v2][v1]을 비교해 답을 도출한다.

 

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static final int INF = 1000000000;
    static int[][] distance = new int[501][501];

    static void FloydWarshall(int n){

        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++)
            Arrays.fill(distance[i], INF);

        for(int i=0; i<k; i++) {
            st = new StringTokenizer(br.readLine());

            int h = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            distance[h][t] = 1;
        }

        FloydWarshall(n);
        
        int s = Integer.parseInt(br.readLine());

        for(int i=0; i<s; i++){
            st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            if(distance[h][t] > distance[t][h]) //뒤의 사건이 먼저 일어났다면
                System.out.println(1);
                
            else if(distance[h][t] < distance[t][h]) //앞의 사건이 먼저 일어났다면
                System.out.println(-1);
                
            else //둘 다 아니라면
                System.out.println(0);
        }
    }
}