[BOJ] 백준 1613번 역사 (Java)

#1613 역사

난이도 : 골드 3

유형 : 그래프 / 플로이드-와샬

1613번: 역사

▸ 문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

▸ 입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

▸ 출력

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

 

문제 풀이  

그래프 최대 크기가 400이하이기 때문에 O(n^3)의 시간복잡도를 가지는 플로이드-와샬 알고리즘을 통해 풀이를 할 수 있다. 모든 정점에 대한 경로를 한번에 조사하여 값을 뽑아주면 된다.

• 플로이드-와샬 알고리즘은 원래 모든 정점에서 다른 모든 정점의 최단 거리를 구할 때 사용하는 알고리즘인데 이와 같이 상태 여부를 조사하는 방법에도 종종 사용하곤 한다.

 

설계

1. a -> b 라고하면 정방향은 -1, 역방향은 1을 저장한다.
2. 플로이드-와샬 알고리즘을 통해 모든 정점에 대한 방향 정보를 입력한다.
   1. map[i][k] == 1 && map[k][j] == 1 이라면, map[i][j] = 1 이다.
   2. map[i][k] == -1 && map[k][j] == -1 이라면, map[i][j] = -1 이다.
3. 사건 쌍의 수 s를 입력받아 각 사건 쌍에 대한 관계를 출력해준다.
   1. map[a][b]

 

풀이 코드 

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

public class Main {
	static int n, a, b;
	static BufferedReader br;
	static StringTokenizer st;
	public static void main(String[] args) throws IOException{
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int kk = Integer.parseInt(st.nextToken());
	
		int[][] map = new int[n+1][n+1];
		for(int i=0; i<kk; i++) {
			input();
			map[a][b] = -1;
			map[b][a] = 1;
		}
		
		for(int k=1; k<n+1; k++) {
			for(int i=1; i<n+1; i++) {
				for(int j=1; j<n+1; j++) {
					if(map[i][k] == 1 && map[k][j] == 1) {
						map[i][j] = 1;
					} else if(map[i][k] == -1 && map[k][j] == -1) {
						map[i][j] = -1;
					}
				}
			}
		}
		
		int s = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<s; i++) {
			input();
			sb.append(map[a][b]+"\n");
		}
		System.out.println(sb.toString());
	}
	
	static void input() throws IOException{
		st = new StringTokenizer(br.readLine());
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
	}
}