[Python] 단어 변환

문제

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

프로그래머스

 

---

풀이 과정

처음 단어에서 목표하는 단어까지 주어진 단어들을 활용하여 최소 변환을 해야 하는 문제이다. (변환을 할 수 없다면 0 반환)
따라서 최단 경로 탐색에 적합한 BFS를 활용하여 문제를 해결하였다. 

코드 과정은 다음과 같다.

1. 처음 시작 단어와 0(단어 변환 횟수)을 queue에 넣는다.
2. queue에서 맨 처음에 있는 단어와 횟수를 뽑는다.
3. 주어진 단어들의 집합에서 아직 사용하지 않은 단어이거나(해당 단어로 변경한 적 없는 경우),
   해당 단어로 변경이 가능한지(알파벳이 하나만 다른지) 검토한다.
4. 3번의 두 조건을 만족한다면 해당 단어를 사용했다는 처리를 해준 후, 다음 단어로 변환할 수 있도록 queue에 [단어(words[i]), 횟수 +1]을 넣는다.
5. 2 - 4번을 queue가 비거나, 목표 단어를 만날 때까지 반복한다.
6. 목표 단어를 만난다면 최소 변환 횟수를 반환하고, 
   queue가 빌 때까지 while 문을 돌았다면 변환할 수 없는 경우이므로 0을 반환한다. 

 

---

코드

from collections import deque

word_l = 0

# 해당 단어로 변환 가능한지 검토 (알파벳 한 개만 다른지 검토)
def possible_change(before_word, after_word):
    diff = 0
    for i in range(word_l):
        if before_word[i] != after_word[i]:
            diff += 1

    if diff == 1:   # 알파벳 한 개만 다르다면
        return True
        
    return False


def solution(begin, target, words):
    global word_l

    word_n = len(words)
    word_l = len(words[0])

    queue = deque([[begin, 0]])

    visited = [0 for _ in range(word_n)]
    while queue:
        word, cnt = queue.popleft()

        if word == target:	# 목표 단어를 만난 경우
            return cnt

        for i in range(word_n):
            if not visited[i]:  # 해당 단어로 변환한 적 없는 경우
                if possible_change(word, words[i]):
                    visited[i] = True
                    queue.append([words[i], cnt + 1])

    return 0    # 변환할 수 없는 경우