[BOJ1613] 역사 (플로이드 워셜)

 

 

---

문제 링크 

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

1613번: 역사

 

문제 풀이 

- 단방향 그래프 

- 주어진 입력에 따라 인접 행렬을 초기화 및 입력 가중치(1) 설정 

- 플로이드 워셜 알고리즘을 실행해서, 각 노드별로 다른 노드 갈 수 있는지 구한다.

- 시간 복잡도 : O(N) 

 

각 케이스에 대해

1) 0 인 경우는 (i, j), (j, i) 둘다 INF로 확인 불가를 뜻함 // 입력 

 

2) 1 인 경우 j와 i 두 값중 i 사건이 더 먼저 발생한 경우를 뜻함

현재 단방향 그래프로 풀이했기 때문에 (i, j)로 갈 수 없고, (j, i)가 양수인 경우를 나타낸다

 

3) -1인 경우 i와 j 두 값중 i 사건이 더 먼저 발생한 경우를 뜻함

현재 단방향 그래프로 생각하여 풀이 했기 때문에 (i, j)의 값이 INF가 아니고 양수인 경우, 즉 i 에서 j로 갈수 있는 경우를 나타낸다

 

예제 입력

5 5
1 2
1 3
2 3
3 4
2 4
3    // 구하려 하는 쿼리 수
1 5 
2 4
3 1

 

플로이드 워셜 수행 결과

0	1	1	2	INF
INF	0	1	1	INF
INF	INF	0	1	INF
INF	INF	INF	0	INF
INF	INF	INF	INF	0

- (1, 5) 의 경우 (1,5) , (5,1) 둘다 INF이기 때문에 답은 0이다 

- (2, 4)의 경우 (2, 4) 갈 수 있으므로 2가 4보다 먼저이므로, 답은 -1 이다

- (3, 1) 의 경우 (3,1) == INF이고, (1,3) = 1 이므로, 1이 3보다 먼저이므로 답은 1이다

 

 

 

참고. https://steady-coding.tistory.com/99

[BOJ] 백준 1613번 : 역사 (JAVA)

 

제출 코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();

    static int n, k, s;

    static int[][] floyd;

    static int INF = 160001;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken()); // 사건의 개수
        k = Integer.parseInt(st.nextToken()); // 전 후 관계 수

        floyd = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            Arrays.fill(floyd[i], INF);
            floyd[i][i] = 0;
        }

        for(int i = 1; i <= k; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            floyd[v1][v2] = 1;
        }

        pro(); // 플로이드 워셜 실행

        s = Integer.parseInt(br.readLine());
        while(s > 0) {
            s -= 1;

            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            int result = 0;
            if(floyd[v1][v2] != INF && floyd[v1][v2] != 0) result = -1;
            else if(floyd[v2][v1] != INF && floyd[v2][v1] != 0) result = 1;

            sb.append(result).append("\n");
        }

        System.out.println(sb);
    }

    static void pro() {
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        input();
    }
    
}