BOJ 15723 - n단 논법

문제

백준 온라인 저지 - 15723번

풀이 과정

n단 논법 을 만족하는지 판단하는 문제입니다.

우선 주어진 논제를 바탕으로 방향 그래프를 생성합니다.
이후 특정 논법이 모순이 없는지 판단하기 위해서는 a is d 일 때 a 에서 d 에 도달 가능한지 판단하면 됩니다.
따라서 생성한 그래프에 플로이드 와샬 알고리즘을 이용해서 모든 정점에 대해 도달 가능성을 판단하면 됩니다.

코드

import sys


N = int(input())
graph = [[0] * 26 for _ in range(26)]
for _ in range(N):
    frm, to = list(sys.stdin.readline().strip().split(' is '))
    graph[ord(frm) - ord('a')][ord(to) - ord('a')] = 1

M = int(input())
questions = []
for _ in range(M):
    frm, to = list(sys.stdin.readline().strip().split(' is '))
    questions.append([ord(frm) - ord('a'), ord(to) - ord('a')])


def floyd():
    global graph

    for k in range(26):
        for u in range(26):
            for v in range(26):
                graph[u][v] = graph[u][v] or (graph[u][k] and graph[k][v])


def solution():
    floyd()

    for frm, to in questions:
        if graph[frm][to]:
            print('T')
        else:
            print('F')


solution()