[ BOJ ] 1613 : 역사 ( GOLD 3 ) / Python

문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

풀이 과정

https://readytojoin.tistory.com/151 10159번 저울과 같은 특징의 문제이다.

전후 관계에 따라 다르게 그래프를 만든다. 먼저 일어난 사건부터 나중에 일어난 사건 순서대로 연결한 그래프 / 나중에 일어난 사건부터 먼저 일어난 사건 순서대로 연결한 그래프 로 나누어 조회할 수 있고, 만약 어느 그래프에도 최단거리 정보가 저장되어 있지 않다면 0 을 출력한다.

import sys
input = sys.stdin.readline
n, k = map(int, input().rstrip().split())
go_graph = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
back_graph = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(k):
    a, b = map(int, input().rstrip().split())
    go_graph[a][b] = 1
    back_graph[b][a] = 1

for i in range(n+1):
    go_graph[i][i] = 0
    back_graph[i][i] = 0


for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            go_graph[a][b] = min(go_graph[a][b], go_graph[a][k] + go_graph[k][b])
            back_graph[a][b] = min(back_graph[a][b], back_graph[a][k] + back_graph[k][b])

s = int(input())
for _ in range(s):
    a, b = map(int, input().rstrip().split())
    if go_graph[a][b] == back_graph[a][b] == float('inf'): print(0)
    elif go_graph[a][b] != float('inf'): print(-1)
    else: print(1)