[Java] 백준 1613 역사

 

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

문제바로가기

1613번: 역사

---

1. 접근방법

 

1. dfs, bfs, 다익스트라, 플로이드워셜로 풀 수 있겠다고 생각이 들었음.

2. 플로이드워셜을 자주 사용안해서 사용하기로 했음.

 

2. 실수

 

값이 뭐가 큰지 헷갈렸다 그러니까 어떤게 더 먼저 일어났는지 헷갈려서 바꿔줬음.

 

3. 코드

 

import java.io.*;
import java.util.*;
public class boj1613 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer stz = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(stz.nextToken());
		int m = Integer.parseInt(stz.nextToken());
		int map[][] = new int[n+1][n+1];
		int a,b;
		for(int i=0;i<m;i++) {
			stz = new StringTokenizer(br.readLine());
			a = Integer.parseInt(stz.nextToken());
			b = Integer.parseInt(stz.nextToken());
			map[a][b] = 1;
		}
		
		for (int k = 1; k <= n; k++) { 
			for (int i = 1; i <= n; i++) { 
				if(i==k || map[i][k] == 0) continue;
				for (int j = 1; j <=n ; j++) { 
					if(map[i][j]==1) continue;
					if(map[k][j]==1) {
						map[i][j] = 1;
					}
				}
			}
		}
		int k = Integer.parseInt(br.readLine());
		for(int i=0;i<k;i++) {
			stz = new StringTokenizer(br.readLine());
			a = Integer.parseInt(stz.nextToken());
			b = Integer.parseInt(stz.nextToken());
			if(map[a][b]==1) sb.append(-1).append("\n");
			else if(map[b][a]==1) sb.append(1).append("\n");
			else if(map[a][b]==0 && map[b][a]==0)sb.append(0).append("\n");
		}
		sb.setLength(sb.length()-1);
		bw.write(sb.toString());
		bw.flush();
	}
}