[Java] 백준 1613번 : 역사

1. 문제

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

1613번: 역사

 

 

 

2. 풀이과정

'관계 = 나보다 뒤에 있다'라고 정의하고 보았다.

 

i => k 이고 k =>j이면 i=>j인 것을 모든 수에 대해 적용시키면 된다. 여기서 i==j일 때는 시작지와 도착지가 같으면 의미가 없으므로 넘긴다. 또, j를 들어가기 전 i=>k부터 성립이 안 되면 앞에서 걸러주면 시간이 단축된다.

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		boolean adjMatrix[][] = new boolean[N+1][N+1];
		
		int K = Integer.parseInt(st.nextToken());
		for(int i=0;i<K;i++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			adjMatrix[n1][n2] = true;
		}
		
		//플로이드
		for(int k=1; k<=N; k++) {
			for(int i=1; i<=N; i++) {
				if(i==k || !adjMatrix[i][k]) continue;
				for(int j=1; j<=N; j++) {
					if(adjMatrix[k][j]) {
						adjMatrix[i][j] = true;
					}
				}
			}
		}
		
		//출력
		int S = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<S;i++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			if(adjMatrix[n1][n2]) {//n1이 먼저 일어났다면
				sb.append(-1).append("\n");
			}
			else if(adjMatrix[n2][n1]) {
				sb.append(1).append("\n");
			}
			else {
				sb.append(0).append("\n");
			}
		}
		System.out.println(sb.toString());
	}
}