문제
역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.
세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.
입력
첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
출력
s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.
풀이
주어진 사건들에 대한 전후 관계를 파악하여 어떤 사건에 대해 해당 사건이 먼저 일어났는지, 뒤에 있는 사건이 먼저 일어났는지, 알지 못하는지를 판단하여 알맞은 값을 출력해야하는 문제로 플로이드-와샬 알고리즘을 사용하여 풀이할 수 있습니다.
지금까지 문제를 풀어보니 대부분의 플로이드-와샬 문제들은 위와 같은 유형을 갖는 것으로 보임.
import sys
# 전처리 부분
input = sys.stdin.readline
# 알고리즘 부분
def floyd():
for i in range(1, n + 1):
for j in range(1, n + 1):
for k in range(1, n + 1):
if not arr[j][k] and arr[j][i] and arr[i][k]:
arr[j][k] = 1
# 메인 코드 부분
n, k = map(int, input().split())
arr = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(k):
a, b = map(int, input().split())
arr[a][b] = 1
floyd()
s = int(input())
temp = [list(map(int, input().split())) for _ in range(s)]
for a, b in temp:
if arr[a][b] == 1:
print(-1)
elif arr[b][a] == 1:
print(1)
else:
print(0)
'🥇 Problem Solving > Floyd warshall' 카테고리의 다른 글
[Python] BOJ / 14938번 / 서강그라운드 (0) | 2022.05.15 |
---|---|
[Python] BOJ / 2660번 / 회장뽑기 (0) | 2022.05.15 |
[Python] BOJ / 10159번 / 저울 (0) | 2022.04.29 |
[Python] BOJ / 1956번 / 운동 (0) | 2022.04.29 |
[Python] BOJ / 2458번 / 키 순서 (0) | 2022.04.17 |