[백준] 2224 명제 증명

문제

• N개의 참인 명제들이 주어졌을 때, 증명될 수 있는 명제 모두 구하기
• 단, "P이면 P이다"와 같이 전건과 후건이 같은 경우는 제외한다.
• 명제들은 알파벳 대소문자 한글자를 사용한다.
• 명제를 출력할 때는 전건 순으로 정렬하고, 전건이 같은 경우에는 후건 순으로 정렬한다.
• 1 <= N <= 10,000

 

풀이

• A => B => C 는 결국 그래프의 연결관계와 같으므로 연결되었는지를 확인하면 된다.
• 알파벳 순서대로 bfs를 통해 연결된 모든 다른 알파벳을 조사한다.
• 시간 단축 Tip
  • num2alpha에 알파벳을 대문자와 소문자 순서로 저장한다.
  • 알파벳을 숫자로 변환하는 함수를 이용해 alpha2num 딕셔너리를 만든다.

 

from collections import deque

# 알파벳을 숫자로 변환 A:0, B:1, ..., Z:25, a:26, ..., z:51
def num(a) :
    return chr(a+65) if a < 26 else chr(a+97-26)

N = int(input())
graph = [[] for _ in range(52)]

num2alpha = [num(i) for i in range(52)]
alpha2num = dict(zip(num2alpha, range(52)))


# 명제 입력 받기
for _ in range(N) :
    a, b = map(str, input().split(" => "))
    graph[alpha2num[a]].append(alpha2num[b])

answer = []
for i in range(52) :    # 알파벳 순서대로 명제 확인
    q = deque([i])
    visited = [False] * 52
    visited[i] = True
    while q:
        now = q.popleft()

        for nxt in graph[now] :
            if not visited[nxt] :
                q.append(nxt)
                visited[nxt] = True

    # 명제 추가
    for nxt in range(52) :
        if visited[nxt] and nxt != i :
            answer.append(f"{num2alpha[i]} => {num2alpha[nxt]}")

print(len(answer))
print(*answer, sep="\n")

 

References

• 백준 최단거리