#백준_1613 역사 - Java 자바

# 유형 : 탐색, 플로이드 와샬

# dfs,bfs 로도 풀 수 있지만 문제를 보면 시작점, 도착점, 중간점을 이용해서 문제를 해결할 수 있다. 예를 들어 1번 사건이 2번 사건보다 먼저 일어났고, 2번 사건이 3번 사건 보다 먼저 일어났다면 1번과 3번중에 먼저 일어난 사건은 1번이다. 플로이드 와샬로 해결해보자면 1번이 시작점, 2번이 중간점, 3번이 도착점이다.

예를 들어 1은 뒤에가 먼저 일어난 사건일 경우, -1은 앞에가 먼저 일어난 사건일 경우, 0은 모르는 경우이다. 따라서 맨 처음에는 모르는 경우로 초기화를 해주고  if(arr[i][j] == 0) {(arr[i][k] == 1 && arr[k][j] == 1 )} ======> arr[i][j] = 1

이런식으로 -1, 1 을 갱신해주면 된다.

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1613 {
    static int N,K,S;
    static int arr[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N+1][N+1];
        for(int i=0; i<K; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            arr[u][v] = -1;
            arr[v][u] = 1;
        }
        
        floyd_warshall();
        
        S = Integer.parseInt(br.readLine());
        for(int s=0; s<S; s++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            System.out.println(arr[u][v]);
        }
        
    }
    
    public static void floyd_warshall() {
        for(int k=1; k<=N; k++) {
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    if(arr[i][j] == 0) {
                        if(arr[i][k] == 1 && arr[k][j] == 1)
                            arr[i][j] = 1;
                        else if(arr[i][k] == -1 && arr[k][j] == -1)
                            arr[i][j] = -1;
                    }
                }
            }
        }
    }
}