[백준] 1613번 - 역사

 

1613번: 역사

 

 

 

문제

 

전체 n개의 역사 속 사건에 대하여 세준이가 알고 있는 두 사건의 전후관계의 수가 k개일 때, s개의 사건 쌍에 대한 전후 관계를 판단하시오.

 

 

 

 

 

조건

 

1 <= n <= 400

1 <= k <= 50,000

1 <= s <= 50,000

시간 제한 1초

사건의 전후 관계가 모순인 경우는 없다.

 

 

 

 

 

풀이 방향

역사 사건을 정점, 세준이가 알고 있는 사건의 전후 관계를 단방향 간선이라고 생각하면 유향 그래프로 치환하여 문제를 해결할 수 있다. 다만, 문제 조건에 사건의 전후 관계가 모순인 경우는 없다고 하였으므로 그래프는 사이클을 형성하지 않는다. 

모든 정점에 대한 최단 거리 및 연결 정보를 알 수 있는 플로이드 - 워셜 알고리즘을 사용하면 문제를 해결할 수 있다. 

 

플로이드 - 워셜 알고리즘 선택 이유

그래프에서 두 정점이 연결되어 있는지 알고 싶은 경우 DFS, BFS, 유니온 파인드, 다익스트라 알고리즘, 플로이드 - 워셜 알고리즘 등을 사용할 수 있다. 그러나 이 문제의 경우 사건의 전후 관계를 알아야 하기 때문에 단순히 연결 정보를 알 수 있는 유니온 파인드 보다는 그 외 방법을 사용하는게 나아 보인다. 또한 입력으로 주어지는 전후 관계가 최대 50,000개이고 전후 관계를 알고 싶은 사건쌍의 수가 50,000개로 시간 제한이 1초라는 점을 감안해 볼 때 다이나믹 프로그래밍 개념을 적용한 다익스트라 알고리즘이나 플로이드 - 워셜 알고리즘을 사용하는 것이 바람직해 보인다. 마지막으로 알고 싶은 사건의 수가 앞서 언급한 것과 같이 50,000 쌍 이하이므로 모든 정점에 대한 최단 거리 및 연결 정보를 알 수 있는 플로이드 - 워셜 알고리즘을 사용하는 것이 가장 적합해 보인다. 플로이드 알고리즘의 시간 복잡도가 O(N^3)인 것을 감안해도 사건의 개수가 최대 400으로 비교적 작기 때문에 시간 제한 조건을 맞출 수 있을 것이다.

 

 

 

플로이드 - 워셜 알고리즘에 대한 작동 방식은 아래 글을 참고하자. 

[백준] 11403번 - 경로 찾기

 

 

 

삼중 반복문의 구조는 위에서 설명한 방식과 매우 유사하지만, 이 문제에서는 최단 경로가 아닌 사건의 전후 관계만을 확인할 수 있으면 되기 때문에 경로에 대한 정보를 저장하는 이중 배열의 타입에 boolean을 사용하였다.

for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
        	// 만약 사건 i와 사건 k의 전후관계를 알고, 사건 k와 사건 j의 전후관계를 안다면 사건 i와 사건 j의 전후관계 또한 알 수 있다. 
            if (event[i][k] && event[k][j]) 
                event[i][j] = true;
        }
    }
}

 

 

 

 

 

 

 

 

 

 

전체 코드

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

public class Main {
    public static void main (String[] args) throws IOException {
        
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = {};
        
        
        input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        
        
        boolean[][] event = new boolean[N+1][N+1];
        
        for (int i = 0; i < K; i++) {
            input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            event[a][b] = true;
        }
        
        
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (event[i][k] && event[k][j]) 
                        event[i][j] = true;
                }
            }
        }
        
        
        StringBuilder sb = new StringBuilder();
        
        int S = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < S; i++) {
            input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            
            if (event[a][b])
                sb.append(-1 + " ");
            else if (event[b][a])
                sb.append(1 + " ");
            else
                sb.append(0);
            
            sb.append("\n");
        }
        
        
        System.out.println(sb);
        
        
        br.close();
    }
}