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

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

프로그래머스

알파벳 한글자만 변환해서 target 단어에 도달하는 bfs문제이다.

 

완전탐색이 아니라 bfs 카테고리에 분류된 이유는 다음과 같다.

1. hit -> hot -> lot, dot ,,

 

2. lot -> log -> cog

2. dot -> dog -> cog

 

처럼 탐색이 진행되기 때문이다.

 

단어를 비교하여 오직 한 알파벳만 차이나는 경우 큐에 담아주고 bfs 탐색을 진행하면 된다.

 

다만 hot -> lot -> hot 처럼 이미 탐색한 단어를 다시 탐색하면 '반드시' 최소로 탐색하지 못하게 된다.

이 때 필요한 것이 '방문처리'인데 이는 파이썬의 dict 자료형을 사용하거나, 아래 코드처럼 인덱스로 접근하여 visited 배열을 이용한 방문 처리를 진행해주면 된다.

from collections import deque

def solution(begin, target, words):
    answer = 0
    length = len(begin)
    dq = deque()
    dq.append([begin,0])
    visited = [False] * len(words)
    
    while dq:
        now,times = dq.popleft()

        if now == target:
            answer = times
            break
            
        for i in range(len(words)):
            cnt = 0
            if words[i] == now : continue
            
            for j in range(length):
                if now[j] != words[i][j]:
                    cnt += 1
            if cnt == 1 and not visited[i]:
                visited[i] = True
                dq.append([words[i],times+1])
                
    return answer