(백준 2224 명제 증명

• tags : (algorithm

  No matching post could be found

  - (floyd-warshall
• 문제 링크 : https://www.acmicpc.net/problem/2224
• 풀이 링크
  • Python

• 명제의 각 조건이 알파벳 대소문자로만 이루어져있고, 명제의 순서도 정해져있다.
• 이를 각 조건 총 52개를 점으로, 각 명제를 그래프에서 선분으로 해석할 수 있다.

• 들어가기 앞서 입력으로 주어지는 알파벳을 더 쉽게 다루기 위한 함수 두개를 먼저 소개하겠다.

def ascii_to_index(x: int) -> int:
    if x < 97:
        return x - 65
    return x - (97 - 26)

def index_to_alp(x: int) -> str:
    if x < 26:
        return chr(x + 65)
    return chr(x + 97 - 26)

• 첫 번째 함수는 주어질 수 있는 최대 52개 문자, A를 인덱스 0으로, a를 인덱스 26으로 지정하는 함수이다.
• 두 번째 함수는 인덱스 형태로 저장한것을 해당 알파벳으로 변환하는 함수이다.

for k in range(52):
    for i in range(52):
        for j in range(52):
            if propositions[i][k] and propositions[k][j]:
                propositions[i][j] = True

• 이후 탐색은 평범한 플로이드 와샬로 진행했고

ans = []
for i in range(52):
    for j in range(52):
        if i != j and propositions[i][j]:
            x, y = index_to_alp(i), index_to_alp(j)
            ans.append(f"{x} => {y}")

• 출력을 위해 다시 순회하며 값을 저장하는데, p => p꼴을 피하기 위한 조건문이 필수로 들어가야한다.