반응형
12-24 00:25
Today
Total
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
관리 메뉴

개발하는 고라니

[백준] 1613번 : 역사 본문

Programming/백준

[백준] 1613번 : 역사

조용한고라니 2021. 2. 26. 01:59
반응형
 

1613번: 역사

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다.

www.acmicpc.net


[플로이드-와샬 (Floyd-Warshall) 알고리즘]

이 문제를 풀기위해 플로이드 와샬 알고리즘을 공부했다. 이 문제를 DFS만으로 풀려고 하니까 TC에서 헤어나오질 못하였다. 사실 당연하다. 최대 정점의 수는 500개이나, 이후 최대 50,000개의 사건이 주어지므로, DFS 1번 당 최대 50,000 재귀를 한다고 할 때, 25,000,000번 호출되지 않을까? 하는 생각이 들었다. 역시 어떻게 풀어야할지 몰라 무식하게 접근한 꼴이다.

 

플로이드 와샬을 이용해 모든 정점에서의 다른 정점으로 가는 최단 경로를 구하여, 주어지는 사건 쌍(v1, v2)가 있으면, distance[v1][v2]와 distance[v2][v1]을 비교해 답을 도출한다.

 

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static final int INF = 1000000000;
    static int[][] distance = new int[501][501];

    static void FloydWarshall(int n){

        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
    }

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

        for(int i=1; i<=n; i++)
            Arrays.fill(distance[i], INF);

        for(int i=0; i<k; i++) {
            st = new StringTokenizer(br.readLine());

            int h = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            distance[h][t] = 1;
        }

        FloydWarshall(n);
        
        int s = Integer.parseInt(br.readLine());

        for(int i=0; i<s; i++){
            st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            if(distance[h][t] > distance[t][h]) //뒤의 사건이 먼저 일어났다면
                System.out.println(1);
                
            else if(distance[h][t] < distance[t][h]) //앞의 사건이 먼저 일어났다면
                System.out.println(-1);
                
            else //둘 다 아니라면
                System.out.println(0);
        }
    }
}
반응형
Comments