[Python - Floyd Warshall] 1613 역사

📌 문제

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

 

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

📌 입력

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

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

역사를 정점으로 생각한다면, 각 정점과 정점의 경로를 모두 비교해야 하는 문제이다. 정점과 정점을 모두 검사하면서 간선의 방향이 같은 경우에 경로를 추가로 갱신해준다.

 

일반적인 플로이드 워셜 알고리즘으로 검사하여 문제를 풀면 된다. b보다 a 사건이 더 먼저 일어났다면, arr[a][b] = -1, arr[b][a] = 1로 갱신해준다. 이런 식으로 값을 초기화해주고, 정점이 특정 정점을 거쳐서 해당 정점으로 가는 경로를 확인해본다. 만약, 1 사건이 2 사건보다 먼저 일어났으며, 2 사건이 5 사건보다 먼저 일어났으면, 1 사건은 5 사건보다 먼저 일어난 것이다. 하지만, 5 사건이 2 사건보다 먼저 일어났다면 1 사건과 5 사건은 둘 중 어느 것이 먼저 일어났는지 알 수 있는 방법이 없다.

 

맥북 에어가 맥북 프로보다 가볍고, 맥북 에어가 엘지 그램보다 가볍다면, 맥북 프로와 엘지 그램의 무게를 비교할 수 있는가? (물론 맥북 프로가 더 무거울 것 같다 ㅎ.ㅎ)

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline
INF = float('inf')
n, k = map(int, input().split())

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for _ in range(k):
    i, j = map(int, input().split())
    graph[i][j] = -1
    graph[j][i] = 1

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if graph[a][k] == graph[k][b] != INF:
                graph[a][b] = graph[a][k]

s = int(input())

for _ in range(s):
    a, b = map(int, input().split())
    if graph[a][b] == INF:
        print(0)
    else:
        print(graph[a][b])

📄 준비

import sys
input = sys.stdin.readline
INF = float('inf')
n, k = map(int, input().split())

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for _ in range(k):
    i, j = map(int, input().split())
    graph[i][j] = -1
    graph[j][i] = 1

내가 내 자신으로 가는 입력, 출력 조건이 없기 때문에 따로 초기화 하지 않고, 입력에 대해서만 초기화한다. 각 사건에 대해 -1과 1로 저장하여 순서를 저장해준다.

📄 풀이

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if graph[a][k] == graph[k][b] != INF:
                graph[a][b] = graph[a][k]

s = int(input())

for _ in range(s):
    a, b = map(int, input().split())
    if graph[a][b] == INF:
        print(0)
    else:
        print(graph[a][b])

이렇게 해서 서로 순서가 같은 경우에 경로를 갱신해준다.

📌 총평

음~ 개꿀 문제 점수 호로록~~! 일 줄 알았지만, 3중 반복문에서 카운팅 변수를 잘못 설정해서 많이 틀렸다 ^_^,,,