BOJ 15723 - n단 논법 (Python)

S1, BFS

문제

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

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

풀이

• 대표적 단방향 그래프 BFS 문제
• 단방향일땐 visited를 굳이 선언하지 않아도 해결할 수 있다.

from sys import stdin
from collections import defaultdict
from collections import deque
n = int(stdin.readline())
graph = defaultdict(list)
for _ in range(n):
    arr = list(map(str, stdin.readline().split()))
    graph[arr[0]].append(arr[2])

m = int(stdin.readline())

def bfs(start, end):
    q = deque(start)
    
    while q:
        x = q.popleft()
        
        if x == end:
            return True
        for node in graph[x]:
            q.append(node)
    
    return False

for _ in range(m):
    arr = list(map(str, stdin.readline().split()))
    if bfs(arr[0], arr[2]):
        print("T")
    else:
        print('F')