백준 1613 - 역사

[문제 바로가기]

 

1. 유형

프롤이드 와샬

 

2. 문제 분석

2-1. 해설

플로이드 와샬을 쓰는 문제였습니다.

N=400이기 때문에, 3중 for문을 돌려도 시간안에 들어옵니다.

플로이드를 사용해서 출발점에서 도착지점 까지의 최단거리를 구해서 저장합니다.

 

맵 초기화

알고리즘 적용 후

S개의 인풋값이 (1,5) (2,4) (3,1)이 주어집니다.

(1,5)는 무한대 이니깐 0출력

(2,4)는 1이니깐 관계를 알 수 있음, -1 출력

(3,1)는 무한대이지만 (1,3)은 관계를 알 수 있음. 1 출력

 

2-2. 설계

2차원 배열을 INF로 초기화 ->  플로이드 와샬 -> 인풋 쌍을 보면서 출력

 

 

3. 코드

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

//https://www.acmicpc.net/problem/1613
//백준 1613번 역사

public class boj_1613_역사 {
	static int INF = 160000;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = stoi(st.nextToken());
		int K = stoi(st.nextToken());
		int m[][] = new int[N][N];
		for (int i = 0; i < N; i++) {
			Arrays.fill(m[i], INF);
		}
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int a = stoi(st.nextToken()) - 1;
			int b = stoi(st.nextToken()) - 1;
			m[a][b] = 1;
		}
		for (int mid = 0; mid < N; mid++) {
			for (int from = 0; from < N; from++) {
				for (int to = 0; to < N; to++) {
					if (from == to)
						continue;
					if (m[from][mid] + m[mid][to] < m[from][to]) {
						m[from][to] = m[from][mid] + m[mid][to];
					}
				}
			}
		}
		st = new StringTokenizer(br.readLine());
		int S=stoi(st.nextToken());
		while (S-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = stoi(st.nextToken()) - 1;
			int b = stoi(st.nextToken()) - 1;
			if(m[a][b]!=m[b][a]) {
				if(m[a][b]!=INF) {
					System.out.println(-1);
				}else
					System.out.println(1);
			}else {
				System.out.println(0);
			}
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}