역사

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

소스코드

Main

public class BOJ1613 {

    static int N,K,A,B;
    static int dist[][];

    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());

        dist = new int[N+1][N+1];

        for (int i = 1; i <=K ; i++) {
            st= new StringTokenizer(br.readLine()," ");
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());

            dist[A][B] = -1;
            dist[B][A] = 1;
            // 숫자가 빠르면 먼저 일어난 역사로 생각한다.
        }


        for (int k = 1; k <N+1 ; k++) {
            for (int i = 1; i <N+1 ; i++) {
                for (int j = 0; j <N+1 ; j++) {
                    if(dist[i][k]== 1 && dist[k][j] ==1){
                    //간선을 거쳐가면서 1이 맞는지 확인 
                        dist[i][j] = 1;
                    }else if(dist[i][k]==-1 && dist[k][j]==-1){
                        dist[i][j] = -1;
                    }
                }
            }
        }

        int c = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < c; i++) {
            st= new StringTokenizer(br.readLine()," ");
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            sb.append(dist[A][B]).append('\n');
        }

        System.out.println(sb.toString());
    }

}

생각할 것

1. 모든 사건의 전후 관계 파악을 위한 프로그램
   모든 노드의 최단거리를 구함 => 플로이드 알고리즘이 생각남.
2. dist 배열 초기화
3. dist 배열에 어떤 값을 넣을지 생각

+@ 비슷한 문제

11404번 - 플로이드 : https://www.acmicpc.net/problem/11404
2606번 - 바이러스 : https://www.acmicpc.net/problem/2606

참고

https://chanhuiseok.github.io/posts/algo-50/