[Python] 백준 #1613 역사

📚문제: #1613 역사(Gold 3)

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

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

입력

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

출력

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

예제

(입력)
5 5
1 2
1 3
2 3
3 4
2 4
3
1 5
2 4
3 1

(출력)
0
-1
1

아이디어 및 구현

• a가 b보다 먼저 일어난 사건이다. 그래프에 반영 후 Floyd-Warshall 알고리즘을 적용한다.

# k줄에 걸쳐 두 사건의 번호가 주어진다.
for _ in range(k):

    # a가 b보다 먼저 일어났음
    a, b = map(int, sys.stdin.readline().split())

    # 그래프 반영
    graph[a][b] = 1

# Floyd-Warshall Algorithm
for k in range(1, n+1):

    for i in range(1, n+1):

        for j in range(1, n+1):

            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

• 사건의 전후 관계를 파악한다.

# 전후 관계를 알고 싶은 사건 쌍의 수 s가 주어진다.
s = int(sys.stdin.readline().rstrip())

# s줄에 걸쳐 번호가 주어진다.
for _ in range(s):

    a, b = map(int, sys.stdin.readline().split())

    # a가 먼저 일어났으면 -1 출력
    if graph[a][b] < INF and graph[b][a] == INF:

        print(-1)

    # b가 먼저 일어났으면 1 출력
    elif graph[a][b] == INF and graph[b][a] < INF:

        print(1)

    # 어떤지 모르면 0 출력 (서로 선후관계가 없을 때, 그래프 상으로는 서로 방문할 수 있는 경로가 없을 때)
    elif graph[a][b] == INF and graph[b][a] == INF:

        print(0)

전체 코드

import sys

# Infinity
INF = int(1e10)

# 사건의 개수 n, 사건의 전후 관계의 수 k가 주어진다.
n, k = map(int, sys.stdin.readline().split())

# 그래프 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]

# 자기 자신과는 0로 초기화
for i in range(1, n+1):

    graph[i][i] = 0

# k줄에 걸쳐 두 사건의 번호가 주어진다.
for _ in range(k):

    # a가 b보다 먼저 일어났음
    a, b = map(int, sys.stdin.readline().split())

    # 그래프 반영
    graph[a][b] = 1

# Floyd-Warshall Algorithm
for k in range(1, n+1):

    for i in range(1, n+1):

        for j in range(1, n+1):

            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

# 전후 관계를 알고 싶은 사건 쌍의 수 s가 주어진다.
s = int(sys.stdin.readline().rstrip())

# s줄에 걸쳐 번호가 주어진다.
for _ in range(s):

    a, b = map(int, sys.stdin.readline().split())

    # a가 먼저 일어났으면 -1 출력
    if graph[a][b] < INF and graph[b][a] == INF:

        print(-1)

    # b가 먼저 일어났으면 1 출력
    elif graph[a][b] == INF and graph[b][a] < INF:

        print(1)

    # 어떤지 모르면 0 출력 (서로 선후관계가 없을 때, 그래프 상으로는 도달할 수 없을 때)
    elif graph[a][b] == INF and graph[b][a] == INF:

        print(0)