[프로그래머스] Python 단어변환 Level3 - DFS/BFS

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

접근

1. 한 번에 한 개의 알파벳만 바꿀 수 있기 때문에 문자열이 하나만 다를 때만 변경이 가능하다.
   ex) hit -> hot (O), hit -> dot (X)
2. words에서 하나씩 꺼내어 현재 단어와 비교하여 1개씩만 바꾸며 최단 경로를 구한다.

슈도코드

단어가 1개만 다른지 체크
	if words의 단어 != 현재 단어:
		카운트 증가
	1인 경우에만 true

for words:
	if (1개만 다르면)
    	words의 단어로 바꾸어주고
        카운트 증가

풀이

from collections import deque

def check_diff(a, b):
    count = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            count += 1
    
    if count == 1: return True
    else: return False

def solution(begin, target, words):
    if target not in words:
        return 0    
    
    q = deque()
    q.append([begin, 0])
    
    while q:
        word, count = q.popleft()
        
        if word == target: 
            return count
        
        for i in range(len(words)):
            temp = words[i]
            if(check_diff(word, temp)):
                q.append([temp, count+1])
    
    return 0