[알고리즘] 백준 9177 '단어 섞기' 풀이 _ 파이썬

백준 9177 단어 섞기
https://www.acmicpc.net/problem/9177
난이도 : 골드 5
유형 : BFS

문제

=> 첫번째 단어와 두번째 단어를 순서 바뀜 없이 섞어서 세번째 단어가 되느냐를 찾는 문제

풀이

처음에 로직을 짤 때 그냥 3번째 단어를 1, 2와 비교하면서 맨 뒤나 맨 앞 알파벳이 서로 일치하면 pop하는 식으로 생각했는데,
1, 2번째 단어에 같은 알파벳이 있을 때의 경우의 수가 갈릴 수 있기 때문에 BFS를 활용해서 풀었다.

1. deque에 1, 2, 3번째 단어의 인덱스 값만 넣으면서 맨 뒤부터 비교한다.
   고로 처음에는 각 단어의 길이를 값으로 넣어준다.
2. 3번째 단어의 맨 뒤 알파벳이 1이나 2번째 단어의 맨 뒤 알파벳과 같으면, 해당 단어 두개의 인덱스를 -1 해준 뒤 deque에 넣어준다. (방문 여부 확인 필수👌)
3. 반복하다가 1, 2, 3 번째 인덱스가 모두 0이 되면 True 를 반환
4. 3번째만 혼자 0이 되면 False, 물론 일치하는 알파벳이 없으면 append 되지 않으므로 deque에 더 이상 값이 없어도 False

정답 코드

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

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

        if ai > 0 and A[ai-1] == C[ci-1] and visited[ai-1][bi] == 0:
            visited[ai-1][bi] = 1
            dq.append([ai-1, bi, ci-1])
        if bi > 0 and B[bi-1] == C[ci-1] and visited[ai][bi-1] == 0:
            visited[ai][bi-1] = 1
            dq.append([ai, bi-1, ci-1])
    else:
        return False

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

처음에 visited 방문 여부 확인을 안해줘서 시간초과가 났었음,, 주의!
문제를 좀 풀다보니 이런 문자열 관련 문제는 배열에 넣어서 스택이나 큐를 활용해서 하나씩 pop 하거나 append 하면서 푸는 풀이가 많이 있다는 걸 알게 되었다.

+) dp를 활용해서 푸는 방법도 있을 것 같다.