문제:
역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.
세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.
입력:
첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
출력:
s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.
풀이방법:
**python3이 아닌 pypy3으로 통과한 문제입니다.**
플로이드-와샬 알고리즘을 적용하면 쉽게 풀 수 있는 문제다. 플로이드-와샬 알고리즘은 주어진 그래프의 경로로 가중치를 초기화한 후 i에서 j로 가는 경로에 k가 추가 되었을 때, 이전의 경로의 가중치보다 작아지는지 확인하면 된다.
이 과정을 마친 후에 a to b가 inf가 아니면 -1을, b to a가 inf가 아니면 1을 inf면 0을 출력하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import sys
n,m = map(int,sys.stdin.readline().split())
MAX = float('inf')
floyd = [[MAX for _ in range(n)]for _ in range(n)]
for _ in range(m):
start,end = map(int,sys.stdin.readline().split())
floyd[start-1][end-1] = 1
for k in range(n):
for i in range(n):
for j in range(n):
floyd[i][j] = min(floyd[i][j],floyd[i][k]+floyd[k][j])
for i in range(int(input())):
a,b = map(int,sys.stdin.readline().split())
if floyd[a-1][b-1] != MAX:
print(-1)
elif floyd[b-1][a-1] != MAX:
print(1)
else:
print(0)
|
cs |
문제링크:
1613번: 역사
첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다.
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]14938. 서강그라운드 (0) | 2021.01.07 |
|---|---|
| [BOJ]1922. 네트워크 연결 (0) | 2021.01.05 |
| [BOJ]13908. 비밀번호 (0) | 2020.12.29 |
| [BOJ]11723. 집합 (0) | 2020.12.24 |
| [BOJ]1527. 금민수의 개수 (0) | 2020.12.22 |