백준 | 1613번. 역사 - 플로이드 문풀

⬛ 백준 1613번. 역사 - 플로이드 문풀

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

1613번: 역사

문제

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

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

입력

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

출력

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

---

💚나의 풀이

• 우선 데이터를 입력받을 떄 map[i][j]에 선후관계에 따라 연결 관계를 담아둔다.
• 플로이드 알고리즘을 사용하여 1~n까지의 경유지 k를 겨쳐서 map[i][k] 와 map[k][j] 가 모두 연결되어있을 경우 map[i][j]에 true 값을 설정해둔다.
• 이제 문제에서 입력하는 s개의 쌍들에 대하여 map에 저장된 값을 기준으로 판별한다.

(1) map[a][b] 가 true 인 경우 : a→b 즉. 앞 번호 먼저 일어났으면 -1 출력

(2) map[b][a] 가 true 인 경우 : b→a 즉, 뒷 번호 먼저 일어나으면 1 출력

(3) 둘 다 아닌 경우는 유추 불가능한 경우이므로 0 출력

package to_0928_8;

import java.util.ArrayList;
import java.util.Scanner;

/*1613번. 역사 - 플로이드 문풀 */
public class Main {	
	static boolean[][] map; //방문 가능한지 담을 거고
	static int n, K, s;
	
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);	
		
		n = kb.nextInt();
		K = kb.nextInt();
		
		map = new boolean[n+1][n+1];
		
		for(int i=0; i<K; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			map[a][b] = true;
		}
		
		//플로이드 워샬 
		for(int k=1; k<=n; k++) {
			for(int i=1; i<=n; i++) {
				for(int j=1; j<=n; j++) {
					//k를 거쳐서 연결되기만 하면 true 처리 
					if(map[i][k] && map[k][j]) {
						map[i][j] = true;
					}
				}
			}
		}
		
		s = kb.nextInt();//쌍의 수 
		ArrayList<Integer> arr = new ArrayList<>();
		
		for(int i=0; i<s; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			
			if(map[a][b] == true) { //a가 먼저 b 나중이면 
				arr.add(-1);
			}else {
				if(map[b][a] == true) {//b먼저 a 다음이면 
					arr.add(1);
				}else {
					//그것도 아니면 아예 연결이 안된 것이므로 
					arr.add(0);
				}
			}
		}		
		//정답 출력 
		for(int x : arr) {
			System.out.println(x);
		}
	}
}