단어변환

접근 방식

BFS로 한글자가 다른 경우 큐에 넣고 순회하기

큰 로직이 어떻게 되는지 그려보면:

queue = [begin]
while queue:
	현재 글자 = queue.popleft()
    	words 순회 - 한 글자가 다르면:
    		queue.append(해당 word)

코드

from collections import deque

def check_word(w1, w2):
    cnt = 0
    for x1, x2 in zip(w1, w2):
        if x1 == x2: cnt += 1
    if cnt == len(w1)-1:
        return True
    else:
        return False

def solution(begin, target, words):
    if target not in words:
        return 0
    
    ans = 0
    queue = deque([(begin, 0)])
    visited = {key : False for key in words}
    while queue:
        cur = queue.popleft()
        if cur[0] == target:
            ans = cur[1] #현재 레벨 저장
            break
        for w in words:
            if visited[w] == False and check_word(cur[0], w):
                queue.append((w, cur[1] + 1))
                visited[w] = True
    return ans

• 레벨 별로 기록을 할 필요가 있어서 큐에 함께 저장했다.
• 정답은 해당 글자를 찾았을 때 레벨