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

백준 15723 - n단 논법

시간 제한 2초, 메모리 제한 128MB

# 조건

• 모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.
• 지무근은 중앙대 컴퓨터공학부 학생이다.
• 그러므로 지무근은 미인이다.

위 연역 논증은 대표적인 삼단논법의 예시이다. 삼단논법이란 전제 두 개와 결론 하나로 이루어진 연역 논증이다. 이것을 응용하면, 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를 출력하라.
• 알 수 없는 경우도 거짓이다.
• 답은 필히 대문자로 출력해야 한다.

# 접근 방법

• 플로이드 워셜 문제이다
• 알파벳 크기 (26) * 26 만큼의 2차원 리스트를 생성한 후 입력을 받는다.
• a is b이면 아스키 변환 -97을 한 값에 1로 기록해준다.
• a->b->c와 같이 어떤 노드 b를 거쳐서 a가 c에 도달할 수 있는 경우, 서로를 연결하면 된다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline


N = int(input())
check = [[float('inf')] * 26 for _ in range(26)]
for _ in range(N):
    a, _, b = map(str, input().strip().split())
    check[ord(a)-97][ord(b)-97] = 1

for k in range(26):
    for i in range(26):
        for j in range(26):
            check[i][j] = min(check[i][j], check[i][k] + check[k][j])

M = int(input())
for _ in range(M):
    a, b = map(str, input().strip().split(' is '))
    if check[ord(a)-97][ord(b)-97] == float('inf'):
        print("F")
    else:
        print('T')