[백준 1613] 역사 (C++/Java)

앞선 사건을 from, 뒤의 사건을 to라 했을 때 단방향이므로 arr[from][to] = 1로 저장하기 (1 아니어도 상관없음. 사건이 일어났다는 표시만 하면 됨.)
플로이드 와샬 알고리즘으로 최단 거리를 구한 후
1) arr[from][to] > 0 && arr[from][to] != INF : 자연수. from이 to보다 앞에 일어났음
2) arr[from][to] >0 && arr[from][to] == INF : 무한대. 어떤 사건이 앞인지 모름
3) arr[from][to] == INF && arr[to][from] >0 : to가 from보다 앞에 일어남

 

 

#include<cstdio>
#define INF 1000000000
int arr[402][402];
int n,k,s,from,to;
int main(void){
    scanf("%d %d", &n, &k);
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++)
            arr[i][j]= (i==j)?0:INF;
    }
    
    for(int i=0; i<k; i++){
        scanf("%d %d", &from, &to);
        
        arr[from][to]=1;
    }
    
    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]>arr[i][k]+arr[k][j])
                    arr[i][j]=arr[i][k]+arr[k][j];
            }
        }
    }
    
    scanf("%d", &s);
    
    for(int i=0; i<s; i++){
        scanf("%d %d", &from, &to);
        
        if(arr[from][to]!=INF && arr[to][from]==INF) printf("-1\n");
        else if(arr[from][to]== INF && arr[to][from]!=INF) printf("1\n");
        else printf("0\n");
    }       
    
    return 0;
}

 

 

- Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main{
    static int maxNum = 987654321;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        int[][] arr = new int[n+1][n+1];
 
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++)
                arr[i][j] = maxNum;
        }
 
        int from=0, to=0;
        for(int i=0; i<t; i++){
            st = new StringTokenizer(br.readLine(), " ");
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
 
            arr[from][to] = 1;
        }
 
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
                }
            }
        }
 
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        for(int i=0; i<tc; i++){
            st = new StringTokenizer(br.readLine(), " ");
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
 
            if(arr[from][to]>0 && arr[from][to]!=maxNum) sb.append("-1").append("\n");
            else {
                if(arr[to][from]>0 && arr[to][from]!=maxNum) sb.append("1").append("\n");
                else sb.append("0").append("\n");
            }
        }
 
        System.out.println(sb);
    }
}