Programmers / 단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

 

Solution

from collections import deque

def solution(begin, target, words):
    answer = 0
    q = deque()
    q.append([begin,0])
    visit = [False]*len(words)
    
    while q:
        word, n = q.popleft()
        if word == target:
            return n
        for idx, w in enumerate(words):
            cnt = 0
            if visit[idx] == False:
                for j in range(len(word)):
                    if word[j] != w[j]:
                        cnt += 1
                if cnt==1:  # 한글자만 다른 경우, q.append()
                    q.append([w,n+1]) # [변환 단어, 변환 횟수]
                    visit[idx] = True
    return 0

BFS로 해결!