[BOJ] Q1613 역사

[BOJ] Q1613 역사

Question

Language: Python

Difficulty: Gold 3

일부분의 전후 관계만을 이용해서 전후 관계에 관한 질문을 답할 수 있냐 없냐하는 문제이다.

전후관계를 노드 간에 간선이 있다고 간주하고, 이를 floyd-warshall을 통해 서로 연결되는 지 여부를 확인한다. 여기서 가장 중요한 부분은 아래의 코드이다.

노드 A-> 노드 B로의 경로가 존재한다면 A 사건이 먼저 발생했음을 의미한다 반대로, 노드 B -> 노드 A에 대한 경로가 존재한다면 이는 B 사건이 먼저 발생했음을 의미한다. 만일, 경로가 없다면 해당 전후관계를 파악할 수 없다는 의미이다.

Prerequisites

if graph[taskA][taskB] != inf:
            print(-1)
        elif graph[taskB][taskA] != inf:
            print(1)
        else:
            print(0)

Solution

from math import inf
def solution():
    for k in range(1,v+1):
        for i in range(1,v+1):
            for j in range(1,v+1):
                temp=graph[i][k]+graph[k][j]
                if temp < graph[i][j]:
                    graph[i][j]=temp

    
    for taskA, taskB in tasks:
        if graph[taskA][taskB] != inf:
            print(-1)
        elif graph[taskB][taskA] != inf:
            print(1)
        else:
            print(0)

if __name__ == "__main__":
    v,e=map(int,input().split())
    graph=[[inf] * (v+1) for _ in range(v+1)]
 
    for _ in range(e):
        v1,v2=map(int,input().split())
        graph[v1][v2]=1
        
    t=int(input())
    tasks=[list(map(int,input().split())) for _ in range(t)]
    
    solution()