[파이썬] 백준 9177번 단어 섞기

백준 #9177 단어 섞기

• 백준 9177번 단어 섞기 문제풀기

• 출력: Data set n: yes / no

• 체크할 조건
  • 1 <= n <= 1000
  • 1 <= (첫 번째, 두 번째 단어 길이) <= 200

• 세 번째 단어의 각 글자를 BFS의 각 층으로 생각하고 BFS 진행
  • w1(첫 번째 단어)와 w2(두 번째 단어)의 초기 인덱스 (0, 0)부터 시작
  • w1과 w2에서 현재 인덱스 (각각 a, b)가 가리키는 문자가 w3(세 번째 단어)의 현재 인덱스가 가리키는 문자와 같다면, 해당 인덱스 순서쌍을 큐에 삽입
• BFS가 모두 완료된 후 w3이 모두 순회되었다면 yes, 아니면 no를 출력한다.

1. 틀린 풀이 (메모리 초과)

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

def solution(n):
    w1, w2, w3 = input().split()
    i = 0
    q = deque([(0, 0)])
    while q:
        for _ in range(len(q)):
            a, b = q.popleft()
            if a < len(w1) and w1[a] == w3[i]:
                q.append((a+1, b))
            if b < len(w2) and w2[b] == w3[i]:
                q.append((a, b+1))
        i += 1
    tf = 'yes' if i == len(w3)+1 else 'no'
    print('Data set {0}: {1}'.format(n, tf))

if __name__ == '__main__':
    for i in range(1, int(input())+1):
        solution(i)

• 이미 체크한 인덱스 순서쌍도 큐에 중복되어 많이 들어가기 때문에 메모리가 초과된다.
  • visited 배열을 이용하여 체크한 인덱스 순서쌍을 중복으로 큐에 들어가지 않게 한다.

2. 정답

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

def solution(n):
    w1, w2, w3 = input().split()
    i = 0
    q = deque([(0, 0)])
    visited = [[0] * (len(w2)+1) for i in range(len(w1)+1)]
    while q:
        for _ in range(len(q)):
            a, b = q.popleft()
            if a < len(w1) and not visited[a+1][b] and w1[a] == w3[i]:
                visited[a+1][b] = 1
                q.append((a+1, b))
            if b < len(w2) and not visited[a][b+1] and w2[b] == w3[i]:
                visited[a][b+1] = 1
                q.append((a, b+1))
        i += 1
    tf = 'yes' if i == len(w3)+1 else 'no'
    print('Data set {0}: {1}'.format(n, tf))

if __name__ == '__main__':
    for i in range(1, int(input())+1):
        solution(i)