[백준] 15723 : n단 논법

https://www.acmicpc.net/problem/15723

15723번: n단 논법

---

• 문제의 조건을 잘 파악한다면, 각 노드(알파벳)는 하나의 노드만 가리킨다고 볼 수 있다.
• 노드가 최대 26개이며 쿼리는 최대 10개이기 때문에, 각 쿼리마다 해당 노드로부터 연결된 모든 노드들을 탐색해도 연산량이 충분히 작다.
• 그대로 구현하면 되는데, 골드 5로 선정된 이유는 플로이드-와샬을 쓰는 경우 때문인 것 같다.
• 모든 노드에 대해 플로이드 와샬을 돌려서 최단 거리가 존재하면 논법이 성립되는 것이다.

---

n = int(input())
logic = [-1] * 26
for i in range(n):          # a 는 b 이면서 c 일 수 없다 == 각 노드는 하나의 노드만 가리킨다
    x, y = map(lambda x: ord(x)-97, input().split(" is "))
    logic[x] = y

m = int(input())
for i in range(m):          # m 이 최대 10개이고, n 은 26개이기 때문에 dfs 돌리듯 논법을 탐색
    visited = [False] * 26
    x, y = map(lambda x: ord(x)-97, input().split(" is "))
    while logic[x] != -1:   # 연결된 논법의 끝까지 탐색
        visited[x] = True
        x = logic[x]
        if visited[x]:      # 논법이 순환하면 
            break
        if x==y:            # 논법 성립하면 종료
            break
    print('T' if x==y else 'F')