[백준-파이썬] 1897: 토달기

문제 보러 가기

접근

BFS로 풀었다. 큐에서 단어를 꺼내면 -> 그 단어에서 토 달기 규칙을 지키면서 사전에 등재된 단어들을 큐 안에 넣어줬다. 이게 check 함수이다. 

어떤 단어(target_word)가 들어오면, 사전을 쭉 ~ 본다. 그러면서 target_word에서 토달기를 했을 때 사전의 해당 단어가 될 수 있다면, 리스트에 넣었다.

일단 토달기는 한 글자만 더할 수 있으니까, 사전의 단어 길이가 target_word+1인지 봤다. 아니라면 continue.
그 다음에 토달기 방식 중에 맨 앞이나 맨 뒤에 한 글자 넣는 경우를 봤다. 단순하게 in으로 체크했다.

마지막으로는 토달기 방식 중 중간에 한 글자 넣은 경우인지 봤다. 이 부분이 젤 까다로운 것 같다. 

target_word에서 토달기를 해서, 사전 해당 단어를 만들 때

 

target_word에서 토달기를 해서, 사전 해당 단어를 못 ! 만들 때

나는 while을 이용해서 사전에서 보고 있는 단어와 target_word의 글자를 하나씩 비교했다. 둘이 겹치면 target_word와 사전 해당 단어의 인덱스를 1 더하고, 안 겹치면 사전 해당 단어의 인덱스만 1 더했다. 사전 단어의 글자들을 하나 하나 끝까지 본 후에, target_word의 인덱스가 어디까지 왔는지 봤다. 만약에 target_word가 끝까지 왔다면, 사전 해당 단어가 target_word에서 글자 하나만 추가 되었고, 나머지는 순서가 다 같다는 뜻이다. 순서가 틀어진다면, target_word 인덱스가 끝까지 오지 못했을 것이다. 

매번 큐에서 꺼낼 때마다 그 단어를 ans로 바꿔줬다. 큐에서 꺼내는 단어는 이전 단어 길이와 같거나, 그것보다 기니까.! 답이 여럿일 경우 어느 것이든 상관 없다고 했으니까 그렇게 갱신해줬다.

 

python으로는 시간 초과ㅠ
pypy로는 통과 !

코드

import collections
import sys

input = sys.stdin.readline

MIIS = lambda: map(int, input().split())
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]

d, first_word = input().split()
words = list(input().strip() for _ in range(int(d)))
ans = 0


# target_word에서 한 글자 토 달기해서 사전에 있는 단어 만들 수 있는지
def check(target_word):
    after_words = []
    target_word_len = len(target_word)
    for word in words:  # 사전의 단어
        # 글자 수 하나만 더 많아야 함
        if (target_word_len + 1) != len(word):
            continue

        # 포함 되면(맨 앞이나 맨 뒤에 붙는 것)
        if target_word in word:
            after_words.append(word)
            continue

        # 중간에 포함되는지
        target_word_idx = 0
        word_idx = 0
        while word_idx < len(word):
            if word[word_idx] == target_word[target_word_idx]:
                target_word_idx += 1
            word_idx += 1
        if target_word_idx == len(target_word):
            after_words.append(word)

    return after_words


# 사전에 있고, 토 달기한 단어를 BFS에 넣어 주기
def bfs():
    global ans

    q = collections.deque()
    q.append(first_word)

    while q:
        word = q.popleft()

        ans = word

        tmp = check(word)
        q.extend(tmp)

    return


bfs()
print(ans)