[백준 2224] 명제 증명 (python)

2224번: 명제 증명

---

 

플로이드-워셜 알고리즘을 사용한다. A -> B, B -> C 일 때, A-> C인가를 확인하는 문제에서 자주 사용된다.

 

1. A(65)를 0, z(122)를 57로 인덱스를 만들어주는 배열 arr를 생성한다.
2. 전, 후가 같은 문자와 같은 명제들은 무시하고 배열에 저장한다.
3. 플로이드-워셜을 사용하여 서로 연결해준다.
4. 연결고리 개수를 출력하고 알파벳 순으로 답을 출력한다.

 

import sys
input = sys.stdin.readline

N = int(input())
arr = [[0]*58 for _ in range(58)]
cnt = 0
for _ in range(N):
    _input = input()
    if _input[0] == _input[5]:
        continue
    if not arr[ord(_input[0])-65][ord(_input[5])-65]:
        arr[ord(_input[0])-65][ord(_input[5])-65] = 1
        cnt += 1

for k in range(58):
    for i in range(58):
        for j in range(58):
            if i != j and not arr[i][j] and arr[i][k] and arr[k][j]:
                arr[i][j] = 1
                cnt += 1

print(cnt)
for i in range(58):
    for j in range(58):
        if arr[i][j]:
            print(chr(i+65) + " => " + chr(j+65))