[programmers] 단어 변환 (python)

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

프로그래머스

---

최단 시간을 구해야 하기 때문에 BFS를 사용해서 풀이하였다.

많이 어렵진 않은 문제

---

from collections import deque

# 두 단어 사이 다른 글자 개수 확인
def check(word1, word2):
    cnt = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
           cnt += 1
    return cnt
    
def solution(begin, target, words):
    answer = 0
    
    # 만약 words에 목표 단어가 없다면 바로 0 반환
    if target not in words:
        return 0
    
    # BFS 진행
    q = deque()
    q.append((begin, 0))
    
    while q:
        n_word, times = q.popleft()
        if n_word == target:
            return times
        
        # 모든 단어를 보면서 바꿀 수 있는 단어라면 바꾸기
        for word in words:
            change = check(word, n_word)
            if change == 1:
                q.append((word, times + 1))