[Python] 백준 1613번 : 역사

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

1613번: 역사

---

💡 문제 풀이

그래프 이론 중 플로이드-워셜 문제이다.

 

이 문제에서는 최소 거리를 따지는게 아니라 순서만 따지면 된다.

따라서, 두 사건 a, b에 대해서 a 다음에 b가 오는지만 따지면 되므로 배열에는 참거짓만 저장해준다.

✔️ 느낀 점

pypy로 제출해야 통과가 되서 다른 분의 코드를 확인해봤는데 전적으로 나와 코드가 유사해서 그냥 넘어가야겠다.

💻 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

graph = [[0] * (N+1) for _ in range(N+1)]    
for _ in range(K):
    start, end = map(int, input().split())
    graph[start][end] = 1
    
for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            if graph[a][k] and graph[k][b]:
                graph[a][b] = 1

S = int(input())
for _ in range(S):
    x, y = map(int, input().split())
    if graph[x][y]: print(-1)
    elif graph[y][x]: print(1)
    else: print(0)