3. 단어 변환 (BFS)

유형 : BFS 

풀이 시간 : 15분

 

from collections import deque 

def solution(begin, target, words):
    answer = 0
    queue = deque()
    queue.append([begin, 0])
    words.insert(0, begin)
    
    visitdict = dict([[word, False] for word in words])
    visitdict[begin] = True

    #최단 거리 - bfs 사용 
    while queue:
        [curr, curcnt] = queue.popleft()
        for word in words:
            dif = 0
            for i in range(len(word)):
                if word[i] != curr[i]:
                    dif += 1
            if dif == 1 and visitdict[word] == False:
                if word == target:
                    answer = curcnt+1
                queue.append([word, curcnt+1])
                visitdict[word] = True
    return answer

 

기본적인 BFS를 사용하여 풀이하였다. 

한 글자만 다른 경우를 필터링하고, 이 경우들을 다음 node로 생각하여 cnt를 증가시켜가며 트리를 순회하도록 하였다.