[Python/파이썬] 프로그래머스 단어 변환

프로그래머스

코드

from collections import deque

def solution(begin, target, words):
    answer = 0
    visited = dict()
    for w in words:
        visited[w] = False
        
    q = deque([(begin, 0)])
    visited[begin] = True
    
    while q:
        now, cnt = q.popleft()
        if now == target:
            return cnt
        # 문자열 비교
        for w in words:
            tmp = 0
            for i in range(len(now)):
                if w[i] != now[i]:
                    tmp += 1
            if tmp == 1 and not visited[w]:
                q.append((w, cnt + 1))
                visited[w] = True
    return 0

BFS로 풀이하였다.

우선 begin 단어를 큐에 넣고 단어에서 한 글자만 바꿔서 변환이 가능한 단어들을 찾아서 큐에 추가해준다. 이때 큐에 추가한 단어들은 방문 처리를 해서 다시 방문하는 일이 없도록 한다.