프로그래머스: 단어 변환 (파이썬, BFS)

변환 횟수가 최소인 경우를 구해야 하므로 BFS로 접근하였다. 처음에 단어들을 어떻게 그래프로 표현할까 하다가 변환 경우의 수를 그려보니 굳이 그래프로 표현 안해도 풀 수 있다는 생각이 들었다. 

 

처음에 테스트케이스3에서 계속 틀렸었는데 그 이유는 두 단어간에 다른 알파벳 갯수를 셀 때 set을 이용해 세었기 때문이다. 그럼 'ccec'같은 단어는 'ce'가 되므로 적절한 비교가 이루어지지 않음을 알 수 있다. 아직 엣지케이스를 생각하는 능력이 부족한 것 같아 그 부분에 대해 좀 더 훈련이 필요하겠다..

 

풀이 코드는다음과 같다. BFS는 넓이를 우선으로 탐색하므로 처음에 begin과 차이가 1인 단어들을 deque에 넣고 그 단어들에 대해 다시 차이가 1인 단어들을 deque에 넣으면 넓이 우선 탐색으로 탐색이 잘 되는 것을 볼 수 있다.

from collections import deque


def difference(word1, word2):
    word2 = list(word2)
    for word in word1:
        if word in word2:
            del word2[word2.index(word)]
    return len(word2)


def solution(begin, target, words):
    if target not in words:
        return 0
    else:
        visited = [False for _ in range(len(words))]
        queue = deque([(begin, 0)])
        while queue:
            cash = queue.popleft()
            if cash[0] == target:
                return cash[1]
            for j in range(len(words)):
                diff = difference(cash[0], words[j])
                if diff == 1 and not visited[j]:
                    queue.append((words[j], cash[1] + 1))
                    visited[j] = True