BOJ#1613 역사
* 문제
* 풀이
플로이드 와셜 알고리즘에 따라
Start -> 임의의 노드 -> End를 만족하는 임의의 노드가 존재할 때 (자기 자신을 포함하여)
Start -> End 를 만족함을 알 수 있습니다.
* 나의 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
boolean[][] edges = new boolean[n][n];
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
edges[a][b] = true;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
edges[i][j] |= edges[i][k] & edges[k][j];
}
}
}
int s = Integer.parseInt(br.readLine());
for (int i = 0; i < s; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
if (edges[a][b]) System.out.println(-1);
else if (edges[b][a]) System.out.println(1);
else System.out.println(0);
}
}
}
'Algorithm > 그래프 탐색' 카테고리의 다른 글
BOJ#2593 엘리베이터 (0) | 2017.10.02 |
---|---|
BOJ#4191 Dominos 2 (0) | 2017.09.10 |
BOJ#2412 암벽 등반 (0) | 2017.09.10 |
BOJ#1963 소수 경로 (0) | 2017.09.05 |
BOJ#1890 점프 (0) | 2017.07.24 |