[알고리즘] 프로그래머스 - 단어 변환

프로그래머스 - 단어 변환

내 풀이

from collections import Counter
import collections

def solution(begin, target, words):
    if target not in words:
        return 0
    visited = collections.defaultdict(int)

    q = collections.deque()
    q.append((begin, 0))
    while q:
        cur, count = q.pop()
        if cur == target:
            return count

        for i in range(len(words)):
            if alpha_diff_one(cur, words[i]) and (visited[words[i]] ==0 or visited[words[i]] >= count + 1):
                q.append((words[i], count + 1))
                visited[words[i]] = count + 1

    return 0


def alpha_diff_one(cur, next_word):
    count = 0
    for i in range(len(cur)):
        if cur[i] != next_word[i]:
            count += 1
    return count == 1


print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]), 4)
print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log"]), 0)
print(solution("hit", "hhh", ["hhh", "hht"]), 2)
print(solution("hit", "hot", ["hot", "dot", "dog", "lot", "log"]), 1)
print(solution("1234567000", "1234567899", [
      "1234567800", "1234567890", "1234567899"]), 3)
print(solution("hit", "cog", ["cog", "log", "lot", "dog", "hot"]), 4) # hit -> hot -> lot -> log -> cog

BFS를 이용해서 풀었다. BFS 중에서도 어렵지 않은 편인데 알고리즘을 꾸준히 안푼지 오래되어 구조를 생각하는데 많이 까먹었고 실수들이 있었다. 다시 감을 회복하려면 꾸준히 풀어야겠다.