[BOJ/Python] 1613_역사

문제 출처:https://www.acmicpc.net/problem/1613

1613번: 역사

문제

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

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

입력

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

출력

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

예제 입력 1

5 5
1 2
1 3
2 3
3 4
2 4
3
1 5
2 4
3 1

예제 출력 1

0
-1
1

---

풀이

 

일부 사건들의 전후 관계를 통하여 주어진 사건들의 전후 관계를 파악하는 문제이다.

일부 사건들의 전후 관계가 존재한다는 것은 사건들을 노드라고 하였을 때, 두 노드를 연결하는 간선이 존재함을 의미한다.

따라서 최종적으로 일부 사건들의 전후 관계를 통하여 노드들의 단방향 그래프를 구할 수 있다.

 

이제 이 그래프를 통하여 주어진 사건들의 전후 관계를 파악하는 경우를 구해야 한다.

만약 A 사건과 B 사건의 전후 관계를 구하는 경우를 생각한다면 다음과 같다.

• A노드(A사건)에서 B노드까지의 경로가 존재한다면 A사건이 먼저 일어난 것이다.
• 만약 그렇지 않고 B노드에서 A노드까지의 경로가 존재한다면 B사건이 먼저 일어난 것이다.
• 만약 둘 다 경로가 존재하지 않는다면 유추할 수 없으므로 0을 출력한다.

 

코드는 다음과 같다.

 

import sys
import heapq
 
INF = int(1e9)
 
def dijkstra(start):
    queue = []
    heapq.heappush(queue,(0,start))
    distance[start][start] = 0
 
    while queue:
        dist, node = heapq.heappop(queue)
        if distance[start][node] < dist:
            continue
 
        for next in graph[node]:
            cost = dist + 1
            if cost < distance[start][next]:
                distance[start][next] = cost
                heapq.heappush(queue,(cost,next))
    
 
n,k = map(int,sys.stdin.readline().split())
 
distance = [[INF for _ in range(n+1)] for _ in range(n+1)]
graph = [[] for _ in range(n+1)]
for _ in range(k):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
 
for i in range(1,n+1):
    dijkstra(i)
 
s = int(sys.stdin.readline())
for _ in range(s):
    a,b = map(int,sys.stdin.readline().split())
    if distance[a][b]!=INF:
        print(-1)
    elif distance[b][a]!=INF:
        print(1)
    else:
        print(0)

• 각 노드들로부터 다른 노드들까지의 거리를 구한다.
• 거리가 INF가 아니라면 해당 노드까지의 경로가 있다는 뜻이다.
• 이를 이용하여 주어진 사건들의 전후 관계를 파악한다.