[백준] 1613 역사 [JAVA]

문제링크 : https://www.acmicpc.net/problem/1613

1613번: 역사

문제 분류가 플로이드 워셜 알고리즘이란 것을 알고서 풀이를 시작한 문제다.

그러나 어떻게 플로이드 워셜로 해결되는지 파악이 안됐었다.

그러다가 최단 거리를 어떻게 갱신하는지 생각해봤다.

플로이드 워셜 알고리즘은 어떤 위치 x가 영향력을 끼치는(x를 지나가면 최단거리가 갱신되는) 모든 a->x->b(1<=x<=n)의 거리를 갱신해 나간다.

이것을 이 문제에서 어떻게 적용할 수 있을지 생각 해보았다.

 

이 문제에서, 어떤 역사적 사건 x가 영향력을 끼치는(x보다 이전 사건, 이후 사건인지) 모든 a > x > b  OR a < x < b를 판단 가능하면 갱신해 나간다.  

플로이드 워셜 알고리즘을 그대로 적용할 수 있는 문제였다.

import java.io.*;
import java.util.*;
public class Main {
	public static int N,M;
	public static int team;
	public static int dist[][];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer (br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		dist = new int[N+1][N+1];
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++){
				dist[i][j] = 0;
			}
		}
		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			dist[a][b] = -1;
			dist[b][a] = 1;
		}
		
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++){
				if(i==j) continue;
				for(int k=1;k<=N;k++){
					if(j==k || i==k) continue;
					if(dist[j][k]==0){
						if(dist[j][i] == dist[i][k] && dist[i][k] == -1 ){
							dist[j][k] = -1;
							dist[k][j] = 1;
						}else if(dist[j][i] ==dist[i][k] && dist[i][k] ==1){
							dist[j][k] = 1;
							dist[k][j] = -1;
						}
					}
				}
			}
		}
		
		int query = Integer.parseInt(br.readLine());
		for(int i=0;i<query;i++){
			st = new StringTokenizer(br.readLine());
			int a= Integer.parseInt(st.nextToken());
			int b= Integer.parseInt(st.nextToken());
			System.out.println(dist[a][b]);
		}

	
	}

}