[프로그래머스] 43163. 단어 변환

Programmers - 43163. 단어 변환

접근

BFS로 구현.

한 스텝마다, deq에 있는 단어들에서 변경할 수 있는 단어 목록을 뽑아와 저장.

그리고 그 목록을 다시 다음 스텝에 deq에서 하나씩 뽑아와서 반복.

 

from collections import deque
def solution(begin, target, words):
    def canChange(fromWord, toWord):
        difChar = 0
        for i in range(len(fromWord)):
            if fromWord[i] == toWord[i]:
                continue
            else:
                difChar += 1

        if difChar == 1:
            return True
        else:
            return False
        
    if target not in words:
        return 0

    step = 0
    deq = deque([begin])
    stepDeq = deque([])

    while deq:
        step += 1

        while deq:
            start = deq.popleft()

            for word in words:
                if canChange(start, word):
                    stepDeq.append(word)

        deq.extend(stepDeq)
        stepDeq.clear()

        if target in deq:
            return step

    return 0