[프로그래머스 - Python3] 단어 변환

Solution

target의 단어를 만들고 count 된 숫자를 return 해야 하기 때문에 BFS를 사용한다.

글자 검사하는 건 반복문으로 하나씩 돌려본다.

 

Code

from collections import deque

def solution(begin, target, words):
	# target하는 단어가 배열에 없으면 0을 return한다.
    if target not in words:
        return 0

    answer = bfs(begin, target, words)
    return answer

def bfs(begin, target, words):
    queue = deque()
    queue.append([begin, 0]) # 시작 단어와 카운트를 처음으로 추가해준다.
    
    while(queue):
        current, cnt = queue.popleft()
        # 지금 단어가 target과 같으면 여태 쌓긴 count 리턴
        if current == target:
            return cnt
        
        for word in words:
            tmp = 0
            for i in range(len(word)):
            	# 한 글자씩 검사한다
                if word[i] != current[i]:
                    tmp += 1
			# 딱 하나만 다르면 queue에 추가
            if tmp == 1:
                queue.append([word, cnt+1])