[BOJ] 9177: 단어 섞기 (Python)

문제 링크

https://www.acmicpc.net/problem/9177

풀이 전략

BFS

1, 2번째 단어에 같은 알파벳이 있을 때의 경우의 수가 갈릴 수 있고, 따라서 BFS를 이용하여 해결할 수 있는 문제입니다.
다음과 같은 로직으로 해결 가능합니다.

1. Queue 에 1, 2, 3번째 단어의 인덱스 값만 넣으면서 맨 뒤부터 비교한다. 따라서 처음에는 각 단어의 길이를 값으로 넣어 준다.

2. 3번째 단어의 맨 뒤 알파벳이 1번째 단어 혹은 2번째 단어의 맨 뒤 알파벳과 같으면, 해당 언어 두 개의 인덱스를 -1 해준 후 Queue 에 넣어 준다. 이 때, 중복 방문 방지를 위해 이차원 배열 visited 을 이용해 방문 여부를 확인해준다.

3. 계속 반복하다가, 1, 2, 3번째 index가 모두 0이 되면 True를 반환한다.

4. 3번째 인덱스만 혼자 0이 되면 False return 하고, Queue 에 더 이상 값이 존재하지 않다는 것은 일치하는 알파벳이 없다는 의미가 되므로, 이 경우에도 False 를 return 한다.

구현

import sys
from collections import deque
input = sys.stdin.readline

def bfs(words):
    A, B, C = words
    Q = deque([(len(A), len(B), len(C))])
    visited = [[0] * (len(B)+1) for _ in range(len(A)+1)]
    
    while Q:
        aa, bb, cc = Q.popleft()
        if aa == bb == cc == 0:
            return True
            
        elif cc == 0:
            return False

        if aa > 0 and A[aa-1] == C[cc-1] and visited[aa-1][bb] == 0:
            visited[aa-1][bb] = 1
            Q.append([aa-1, bb, cc-1])
            
        if bb > 0 and B[bb-1] == C[cc-1] and visited[aa][bb-1] == 0:
            visited[aa][bb-1] = 1
            Q.append([aa, bb-1, cc-1])
    else:
        return False

n = int(input())
for i in range(n):
    words = list(map(str, input().split()))
    if bfs(words):
        print(f"Data set {i+1}: yes")
    else:
        print(f"Data set {i+1}: no")