[프로그래머스] 단어 변환 (python)

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

코딩테스트 연습 - 단어 변환

---

📍 Problem

단어 begin 에서 target으로 변환하는 가장 짧은 순서를 찾는다. 

1. 한 번에 한 개의 알파벳만 바꿀 수 있으며

2. 주어진 words에 있는 단어로만 변환할 수 있다.

ex. 

begin	target	words	최소 변환 과정	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	"hit" -> "hot" -> "dot" -> "dog" -> "cog"	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	x	0

 

---

💡 Solution

현재 단어로부터 변환 가능한 단어를 다음 node로 추가하며 target 단어가 되는 최소 거리를 찾는 BFS로 접근하면 된다.

 

두 단어가 변환 가능한지 (한 알파벳만 다른지) 체크하는 함수를 두고,

다음 방문할 단어를 선택할 때 이미 선택된적이 있는 단어인지, 변환 가능한 단어인지 확인한다. 

from collections import deque


def is_valid(word, target):
    # 한 개의 알파벳만 다른지 체크
    diff_cnt = 0
    for i in range(len(target)):
        if word[i] != target[i]:
            diff_cnt += 1
        if diff_cnt > 1:
            return False
    return True


def solution(begin, target, words):
    q = deque()
    visited = {}

    for word in words:
        if is_valid(begin, word):
            q.append(word)
            visited[word] = 1

    while len(q) > 0:
        node = q.popleft()
        if node == target:
            return visited[node]
        for word in words:
            if word in visited or not is_valid(node, word):
                continue
            q.append(word)
            visited[word] = visited[node] + 1
    return 0


if __name__ == '__main__':
    begin = 'hit'
    target = 'cog'
    words = ["hot", "dot", "dog", "lot", "log", "cog"]
    sol = solution(begin, target, words)
    print(sol)