DHistory
[Baekjoon] Shortest Path - 15723 n단 논법 본문
문제
15723번: n단 논법
m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다.
www.acmicpc.net
풀이
n단 논법이므로, 시작 단계에서 중단 단계를 거쳐 마지막 단계로 지나가는 길을 찾으면 된다. (= floyd warshall)
(주의사항) 각 전제는 단방향이다.
import sys
INF = 1e9
n = int(sys.stdin.readline().rstrip())
distance = [[INF] * 26 for _ in range(26)]
for _ in range(n):
x, y = sys.stdin.readline().rstrip().split(' is ')
# 단방향
distance[ord(x) - ord('a')][ord(y) - ord('a')] = 1
m = int(sys.stdin.readline().rstrip())
results = []
for _ in range(m):
x, y = sys.stdin.readline().rstrip().split(' is ')
results.append((x, y))
for k in range(26):
for i in range(26):
for j in range(26):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
for x, y in results:
print('T' if distance[ord(x) - ord('a')][ord(y) - ord('a')] != INF else 'F')
채점 결과
'Computer Science > Algorithm' 카테고리의 다른 글
| [Baekjoon] Greedy - 1041 주사위 (0) | 2023.11.01 |
|---|---|
| [Baekjoon] Topology Sort - ACM Craft (0) | 2023.10.31 |
| [Baekjoon] Shortest Path - 1446 지름길 (0) | 2023.10.31 |
| [Baekjoon] Shortest Path - 1389 케빈 베이컨의 6단계 법칙 (0) | 2023.10.30 |
| [Baekjoon] Shortest Path - 11403 경로 찾기 (0) | 2023.10.30 |