[알고리즘] 플로이드-와샬 알고리즘 사용 시 주의점 (BOJ2224 - Python)

백준 2224번을 풀며 플로이드-와샬 알고리즘을 사용할 때 주의해야 할 점을 깨닫게 되었고,

이를 잊지 않기 위해서 이렇게 글로 남긴다.

 

사투의 흔적

 

플로이드-와샬 알고리즘

---

이 알고리즘이 무엇인지에 대해서는 이전에 작성한 글을 참고하길 바란다.

[알고리즘] 플로이드-와샬(Floyd-Warshall) 알고리즘

 

 

문제

---

2224번: 명제 증명

 

 

풀이

---

첫 (틀린) 풀이

맨 처음에 작성한 풀이이다.

정말 단순하게, 그래프를 탐색하는 것 마냥 P → Q  → R가 되는 것을 찾으려고 하였다.

import sys

input = sys.stdin.readline

N = int(input().strip())
X = 0  # 출력할 명제의 개수

props, proofs = dict(), dict()
for _ in range(N):
    P, _, Q = map(str, input().split())
    if P != Q:
        if P in props:
            if Q not in props[P]:
                props[P].append(Q)
                proofs[P].add(Q)
        else:
            props[P] = [Q]
            proofs[P] = set(Q)
        X += 1

for P in props.keys():  # P
    for Q in props[P]:  # Q
        if Q in props:
            for R in props[Q]:  # R
                if P != R:
                    proofs[P].add(R)
                    X += 1

Ps = list(proofs)
Ps.sort()

print(X)
for P in Ps:
    Rs = list(proofs[P])
    Rs.sort()
    for R in Rs:
        print(P + " => " + R)

 

처음에는 4%에서 '틀렸습니다'가 떴고,

주어진 명제들 입력을 받는 부분(아래 코드 참고)에서 'if P != Q:'를 추가하는 것으로 9%에서 '틀렸습니다'가 뜨게 되었다.

props, proofs = dict(), dict()
for _ in range(N):
    P, _, Q = map(str, input().split())
    if P != Q:  # 추가한 부분
        if P in props:
            if Q not in props[P]:
                props[P].append(Q)
                proofs[P].add(Q)
        else:
            props[P] = [Q]
            proofs[P] = set(Q)
        X += 1

 

파이썬에서 자동으로 대문자, 소문자를 구별해줄 것 같아서 따로 처리를 해주지 않았다.

이것 때문에 틀렸다고 생각되어 풀이를 변경하게 되었다.

 

플로이드-와샬 (틀린) 풀이

A~Z, a~z 순으로 이들을 한 배열로 표현하기 위해 Alpha2Idx(), Idx2Alpha() 두 함수를 만들어 사용하였고,

플로이드-와샬 알고리즘을 통해 삼단 논법을 적용하여 참인 명제들을 찾아내려 하였다.

 

아래 코드에서 어느 부분이 틀린 것인지 생각해보라.

import sys

input = sys.stdin.readline

N = int(input().strip())
props = [[False for _ in range(52)] for _ in range(52)]  # P(행) → Q(열)가 참이라면 True


# A : 65 ~ Z : 90 → idx : 0 ~ 25
# a : 97 ~ z : 122 → idx : 26 ~ 51

def Alpha2Idx(alpha):
    asciiNum = ord(alpha)  # Ascii2Num
    if 65 <= asciiNum <= 90:
        return asciiNum - 65
    return asciiNum - 71


def Idx2Alpha(idx):
    if 0 <= idx <= 25:
        return chr(idx + 65)  # Num2Ascii
    return chr(idx + 71)


for _ in range(N):  # 주어진 명제들 입력 받기
    P, , Q = map(str, input().split())
    if P != Q:
        props[Alpha2Idx(P)][Alpha2Idx(Q)] = True

# 삼단 논법 적용
for P in range(52):
    for Q in range(52):
        for R in range(52):
            if P == Q or Q == R or R == P:
                continue
            if props[P][Q] and props[Q][R]:  # 삼단 논법
                props[P][R] = True

# 참인 명제들 저장
proofs = []
for P in range(52):
    for Q in range(52):
        if P != Q and props[P][Q]:
            proofs.append((P, Q))

# 출력
print(len(proofs))
for P, Q in proofs:
    print(Idx2Alpha(P) + " => " + Idx2Alpha(Q))

 

틀린 부분은 플로이드-와샬 알고리즘에서 삼단 논법을 적용한 부분이다.

# 삼단 논법 적용
for P in range(52):
    for Q in range(52):
        for R in range(52):
            if P == Q or Q == R or R == P:
                continue
            if props[P][Q] and props[Q][R]:  # 삼단 논법
                props[P][R] = True

 

이렇게 3중 포문을 쓰면 자연스럽게 P → Q, Q → R가 될 것 같지만 아니다.

맨 위가 거쳐가는 노드이기 때문이다.

 

 

따라서 해당 부분은 다음과 같이 고쳐야 한다.

# 삼단 논법 적용
for Q in range(52):
    for P in range(52):
        for R in range(52):
            if P == Q or Q == R or R == P:
                continue
            if props[P][Q] and props[Q][R]:  # 삼단 논법
                props[P][R] = True

 

플로이드-와샬 (맞은!) 풀이

import sys

input = sys.stdin.readline

N = int(input().strip())
props = [[False for _ in range(52)] for _ in range(52)]  # P(행) → Q(열)가 참이라면 True


# A : 65 ~ Z : 90 → idx : 0 ~ 25
# a : 97 ~ z : 122 → idx : 26 ~ 51

def Alpha2Idx(alpha):
    asciiNum = ord(alpha)  # Ascii2Num
    if 65 <= asciiNum <= 90:
        return asciiNum - 65
    return asciiNum - 71


def Idx2Alpha(idx):
    if 0 <= idx <= 25:
        return chr(idx + 65)  # Num2Ascii
    return chr(idx + 71)


for _ in range(N):  # 주어진 명제들 입력 받기
    P, _, Q = map(str, input().split())
    if P != Q:
        props[Alpha2Idx(P)][Alpha2Idx(Q)] = True

# 삼단 논법 적용
for Q in range(52):
    for P in range(52):
        for R in range(52):
            if P == Q or Q == R or R == P:
                continue
            if props[P][Q] and props[Q][R]:  # 삼단 논법
                props[P][R] = True

# 참인 명제들 저장
proofs = []
for P in range(52):
    for Q in range(52):
        if P != Q and props[P][Q]:
            proofs.append((P, Q))

# 출력
print(len(proofs))
for P, Q in proofs:
    print(Idx2Alpha(P) + " => " + Idx2Alpha(Q))

 

 

깨달음

---

이전에 플로이드-와샬 알고리즘에 대해 알아보면서 작성했던 글에도 나와있었는데, 아주 새까맣게 잊고 있었다.

# 플로이드-와샬 알고리즘
for k in range(N):  # k : 거쳐가는 노드
    for i in range(N):  # i : 출발 노드
        for j in range(N):  # j : 도착 노드
            if dp[i][k] + dp[k][j] < dp[i][j]:
                dp[i][j] = dp[i][k] + dp[k][j]  # 갱신

 

플로이드-와샬 알고리즘은 '거치는 노드 하나를 잡아두고 for문을 돌린다'라고 생각해놓도록 하자!

special thanks to JW