2021.2.26 [백준] 명제 증명

플로이드 워셜 알고리즘

 

 

Q

 

www.acmicpc.net/problem/2224

2224번: 명제 증명

 

A

 

플로이드 워셜로 푸는데 상당히 고민했다. P => P 같은 경우는 출력하지 않기로 한다는 조건을 빼먹어서 애먹었고, 출력할 명제 갯수 세는데도 고생했었다.

 

코드

 

import sys

INF = int(1e9)

n = int(sys.stdin.readline().rstrip())

graph = [[INF] * (123) for _ in range(123)] #ord('a')=97, ord('A')=65, ord('z')=122, ord('Z')=90 이므로 알파벳 다 포함시키려면 123으로 잡기

 

for _ in range(n):

    x, b, y = map(str, sys.stdin.readline().rstrip())

    x = int(ord(x))

    y = int(ord(y))

    graph[x][y] = 1 #비용은 정해져 있지 않고, 증명이 된다는 걸 표시하면 되므로 1로 설정

 

for k in range(123): #점화식 실행
    for i in range(123):
        for j in range(123):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
            

count = 0 #출력할 명제 갯수 세는 용도
for i in range(123):
    for j in range(123):
        if graph[i][j] < INF and i != j: #i와 j가 다를 때를 조건으로 한 이유는 문제에서 같은 것은 출력하지 않기로 함
            count += 1

print(count) #명제 갯수 출력
for i in range(123):
    for j in range(123):
        if graph[i][j] < INF and i != j: #i와 j가 다를 때를 조건으로 한 이유는 문제에서 같은 것은 출력하지 않기로 함
            print(chr(i), '=>', chr(j)) #명제 출력