알고리즘 고득점 Kit - DFS/BFS - 단어 변환

문제 풀이

1. 단어를 바꾸는 change 함수를 만들어 줌(현재 단어와 words의 i번째 단어를 비교)
2. deque에 0, 시작단어를 넣고 while문을 돌림 - 종료 조건 : 현재 단어와 타겟 단어가 같은 경우
3. 바꾼 단어는 다시 돌아가지 않기 위해 visited 사용
4. while문 종료 이후 answer값이 바뀌지 않았다면 0을 반환, 아니라면 answer를 반환

from collections import deque
def change(start, end):
    cnt = 0
    for i in range(len(start)):
        if start[i] == end[i]:
            cnt += 1

    if cnt == len(start)-1:
        return 1
    else:
        return 0

def solution(begin, target, words):
    answer = 100
    q = deque([(0, begin)])
    visited = [False] * len(words)

    while q:
        cnt, now = q.popleft()

        if now == target:
            answer = cnt

        for i in range(len(words)):
            if change(now, words[i]) and visited[i] == False:
                q.append((cnt+1, words[i]))
                visited[i] = True

            else:
                continue
    if answer == 100:
        return 0
    return answer