[백준] 1613번 역사

💡문제접근

• 플로이드-워셜 알고리즘을 이용한 문제
• a가 b보다 먼저 발생했는지 즉, graph[a][b]가 1이면 -1
• b가 a보다 먼저 발생했는지 즉, graph[b][a]가 1이면 1
• 만약 graph[a][b]가 INF라면 알 수 없으므로 0
• Python3로는 시간초과, PyPy3로는 AC

💡코드(메모리 : 118180KB, 시간 : 652ms, PyPy3로 제출)

import sys
input = sys.stdin.readline
INF = int(1e9)

n, k = map(int, input().strip().split())
graph = [[INF] * (n+1) for _ in range(n+1)]

for _ in range(k):
    a, b = map(int, input().strip().split())
    graph[a][b] = 1

for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

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] + graph[k][b] == 2:
                graph[a][b] = 1

s = int(input())
for _ in range(s):
    a, b = map(int, input().strip().split())
    if graph[a][b] == 1:
        print(-1)
    elif graph[b][a] == 1:
        print(1)
    elif graph[a][b] == INF:
        print(0)

💡소요시간 : 14m