[백준] 1613번. 역사(JAVA)

문제

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

---

풀이(45분)

import java.io.*;
import java.util.*;

public class Main {

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

        boolean[][] arr = new boolean[N + 1][N + 1];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[x][y] = true;
        }

        // 플로이드-와샬 알고리즘
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (arr[i][k] && arr[k][j]) {
                        arr[i][j] = true;
                    }
                }
            }
        }

        int S = Integer.parseInt(br.readLine());

        for (int i = 0; i < S; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            if (arr[x][y]) {
                System.out.println(-1);
            } else if (arr[y][x]) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
    }
}

---

문제 풀이 전략

 

플로이드-와샬 알고리즘 이라는 것을 생각하는데 시간이 좀 걸렸다.

dfs를 했지만 400번의 뎁쓰에 의해 스택오버플로우가 발생했고, dp로는 해결하지 못했다.

 

플로이드 와샬 알고리즘 도입 전략은 다음과 같다.

1. n = 400이기때문에 O(n^3)의 시간 복잡도를 만족할 수 있다.

2. 모든 정점에서 모든 정점으로 이어질 수 있나를 봐야한다.