[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()
댓글남기기