문제 링크

역사

문제 설명

역사 사건의 전후를 파악하려고 한다. 일부 사건의 전후 관계가 주어질때, 특정 사진의 전후 관계를 파악하라.

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

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

문제 풀이

전후사건이라고 해서 오 이번주에 공부한 위상정렬 써먹는 문젠가?! 했는데 cyclic graph기 때문에 위상정렬을 써먹을 수는 없다. 모든 노드에서 모든 노드까지 가는 최단 거리를 구하는 플로이드-워셜 알고리즘을 사용하면 쉽게 풀 수 있다.

graph[a][b] : a->b까지 갈 수 있으면 0, 없으면 INF

import sys
from collections import deque

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

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

#자기 자신에서 자기 자신으로 가는 경우
for i in range(1, n+1):
    graph[i][i] = 0

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

for i in range(1, n+1):
    #각각의 노드에 대해 거쳐가는 경우
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][i]+graph[i][b])


s = int(input())
for _ in range(s):
    a, b = map(int, input().split())
    if graph[a][b] == 0:
        #a->b
        answer.append(-1)
    elif graph[b][a] == 0:
        #b->a
        answer.append(1)
    else:
        answer.append(0)

for a in answer:
    print(a)

구현 자체는 어렵지 않은데 플로이드-워셜을 써먹어야 겠다고 생각하내는게 어려웠다.