[프로그래머스] / [Level 3] / [Python] 단어 변환

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

프로그래머스

---

BFS를 사용하여 해결하였다.

시작 단어와 방문하지 않은 단어들을 하나씩 삽입하여 목표 단어에 도달 할 때 까지 탐색하도록 구성하였다.

ischangable 함수는 두 단어가 변환 가능한지 판단하도록 하는 함수이다.

from collections import deque

def ischangable(a, b):
    count = 0
    
    for _a, _b in zip(a, b):
        if _a == _b:
            count += 1
    
    if count == len(a)-1:
        return True
    else:
        return False

def bfs(i, words, visited, target):
    visited[i] = True
    
    q = deque()
    q.append([i, 0])

    while q:
        pop = q.popleft()
        visited[pop[0]] = True

        for j in range(len(words)):
            if visited[j] == False:
                if ischangable(words[pop[0]], words[j]):
                    q.append([j, pop[1]+1])

                    if words[j] == target:
                        return pop[1] + 1
                

def solution(begin, target, words):
    if target not in words:
        return 0

    visited = [False for _ in range(len(words)+1)]
    
    words = [begin] + words
    
    return bfs(0, words, visited, target)