2224번: 명제 증명
첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전건 순으로 정렬하고, 전건이 같은 경우에는 후건 순으
www.acmicpc.net
플로이드-워셜 알고리즘을 사용한다. A -> B, B -> C 일 때, A-> C인가를 확인하는 문제에서 자주 사용된다.
- A(65)를 0, z(122)를 57로 인덱스를 만들어주는 배열 arr를 생성한다.
- 전, 후가 같은 문자와 같은 명제들은 무시하고 배열에 저장한다.
- 플로이드-워셜을 사용하여 서로 연결해준다.
- 연결고리 개수를 출력하고 알파벳 순으로 답을 출력한다.
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))
'개발 > 알고리즘' 카테고리의 다른 글
[백준 3025] 돌 던지기 (1) | 2021.09.08 |
---|---|
[백준 11723] 집합 (java) (0) | 2021.08.12 |
[백준 2638] 치즈 (python) (0) | 2021.06.02 |
[백준 16719] ZOAC (python) (0) | 2021.05.31 |
[백준 9934] 완전 이진 트리 (python) (0) | 2021.05.31 |
최근댓글