BOJ 1613 - 역사

문제

백준 온라인 저지 - 1613번

풀이 과정

역사의 한 지점을 그래프의 정점으로 나타내면 각 사건의 전후 관계는 정점의 도달성 문제로 생각할 수 있습니다.

따라서 정점의 최대 개수가 400개 이하이므로 O(N^3) 의 시간복잡도를 가지는 플로이드 와샬 알고리즘 을 활용하여 문제를 해결했습니다.
모든 정점간의 도달성 여부를 계산해준 뒤, 문제에서 주어지는 입력의 전후 관계를 출력해주도록 했습니다.
다만 Python3 의 속도 한계로 인해 PyPy로 제출해야 시간제한 이내에 수행이 가능했습니다.

코드

import sys


n, k = list(map(int, sys.stdin.readline().split()))
adj = [[0]*n for _ in range(n)]
for _ in range(k):
    frm, to = list(map(int, sys.stdin.readline().split()))
    adj[frm-1][to-1] = 1
s = int(input())
event = []
for _ in range(s):
    line = list(map(int, sys.stdin.readline().split()))
    event.append(line)


def floyd():
    global adj

    for k in range(n):
        for u in range(n):
            for v in range(n):
                adj[u][v] = adj[u][v] or (adj[u][k] and adj[k][v])


def solution():
    floyd()
    for e in event:
        if adj[e[0]-1][e[1]-1]:
            print(-1)
        elif adj[e[1]-1][e[0]-1]:
            print(1)
        else:
            print(0)


solution()