[Python/파이썬] 백준 15723번 n단 논법

15723번: n단 논법

 

문제

모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.

지무근은 중앙대 컴퓨터공학부 학생이다.

그러므로 지무근은 미인이다.

위 연역 논증은 대표적인 삼단논법의 예시이다. 삼단논법이란 전제 두 개와 결론 하나로 이루어진 연역 논증이다. 이것을 응용하면, n개의 전제가 있을 때 m개의 결론을 도출할 수 있을 것이다. 이때의 n과 m은 모든 의미에서 적절한 수라고 가정하자. 자세한 것은 입출력 예시를 확인하자.

입력

첫째 줄에 정수 n(2 ≤ n ≤ 26)이 주어진다.

둘째 줄부터 n개의 줄에 걸쳐 각 줄에 전제가 하나씩 주어진다. 전제는 모두 a is b의 형식으로 주어지며 a와 b는 서로 다른 임의의 알파벳 소문자이다. 특별한 명시는 없지만 모든 전제는 “모든 a는 b이다”라는 의미이다. 하지만 “모든 b는 a이다”의 의미는 될 수 없다. 또한 a는 b이면서 c일 수 없으나, a와 b가 동시에 c일 수는 있다.

n + 2번째 줄에 정수 m(1 ≤ m ≤ 10)이 주어진다. 그 다음 m개의 줄에 걸쳐 각 줄에 하나의 결론이 전제와 같은 형식으로 주어진다.

출력

m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다.

코드

n = int(input())
graph = dict()
for i in range(n):
    a, _, b = list(input().split())
    graph[a] = b

m = int(input())
for i in range(m):
    a, _, b = list(input().split())

    visited = set()
    while True:
        if a not in graph or a in visited:
            print("F")
            break
        if graph[a] == b:
            print("T")
            break
        visited.add(a)
        a = graph[a]

 

처음에는 이렇게 연결된 노드를 무작정 탐색하도록 했는데, 다 풀고 알고리즘 분류를 보니 다양한 방법으로 풀 수 있길래 플로이드 워셜을 이용해서도 풀어보았다.

 

INF = int(1e9)

n = int(input())
distances = [[INF]*26 for _ in range(26)]
for i in range(n):
    a, _, b = input().split()
    a = ord(a)-97
    b = ord(b)-97
    distances[a][b] = 1

# 플로이드-워셜
for k in range(26):
    for i in range(26):
        for j in range(26):
            distances[i][j] = min(
                distances[i][j], distances[i][k]+distances[k][j])

m = int(input())
for _ in range(m):
    a, _, b = input().split()
    a = ord(a)-97
    b = ord(b)-97
    print("T" if distances[a][b] < INF else "F")

이렇게 하면 a~z까지 모든 알파벳 간의 관계의 거리를 구할 수 있다. 거리가 초기값인 INF와 같다면 성립할 수 없는 결론이라는 뜻이고, INF보다 작다면 성립할 수 있다는 뜻이다.