(Python) 프로그래머스 - 단어 변환

09 Mar 2022 in Algorithm on Programmers, Level3

[문제 링크]

풀이

from collections import deque


def solution(begin, target, words):
    if target not in words:
        return 0

    INF = int(1e9)
    answer = INF
    visited = dict()
    visited[begin] = 0
    q = deque()

    q.append(begin)
    while q:
        for _ in range(len(q)):
            origin = q.popleft()
            for next in diff_words(origin, words):
                if next == target:
                    return visited[origin] + 1

                if next not in visited:
                    visited[next] = visited[origin] + 1
                    q.append(next)

    if answer == INF:
        answer = 0

    return answer


def diff_words(origin, words):
    for word in words:
        cnt = 0
        for x, y in zip(origin, word):
            if x != y:
                cnt += 1

        if cnt == 1:
            yield word

처음에는 permutation으로 풀었는데 시간초과가 발생했다.
시간을 줄일 수 있는 방법은 그때그때 딱 1개만 차이나는 문자를 찾아서 해결하는 방법이었기에 bfs로 풀었다.
diff_words에서 리턴값을 리스트로 모아서 리턴해줘도 되지만 yield를 사용하면 그때그때 맞는 것을 여러 번 리턴하면서 제너레이터로 반환한다.