[프로그래머스][Python] 단어 변환

문제를 정리해보자.

 

시작단어, 목표단어, words가 주어진다. 시작단어를 목표단어가 되도록 변환해야 한다.

아래와 같은 규칙으로 단어를 변환할 수 있다.

 

 

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

 

 

시작단어가 목표단어가 되기 위해 몇 단계가 필요한가?

 

프로그래머스에 있는 예를 보자.

 

시작단어 : "hit"

목표단어 : "cog"

words :  ["hot","dot","dog","lot","log","cog"]

 

 "hit" -> "hot" -> "dot" -> "dog" -> "cog" 이렇게 4단계가 필요하다.

 

 

풀이를 생각해보자.

 

위의 예에서, 자리 별로 바꿀 수 있는 알파벳을 생각해보자.

 

첫 번째 : h, d, l, c

두 번째 : o

세 번째 : t, g

 

변환해보자.

 

지금단어 : hit

첫 번째 변환 : hit, dit, lit, cit,

두 번째 변환 : hot

세 번째 변환 : hit, hig

 

즉, hit 단어는 총 7번 변환할 수 있다.

그런데 변환된 hot단어만 words안에 있는 단어이다.

때문에 지금단어를 hot단어로 바꾸고 또 변환한다.

 

변환해봤던 단어는 다시 변환하지 않는다.

만약 다시 변환이 가능하게 된다면 무한루프에 빠져서, 목표단어를 만들 수 없는 경우를 잡을 수 없다.

 

 

 

 

 

구현해보자.

 

BFS로 구현했다. 

 

 

from collections import deque


def solution(begin, target, words):
    # 입력
    l = len(words[0])  # 단어 길이
    alpha = [[] for _ in range(l)]  # 자리 별 알파벳 모음
    words_li = {}  # 변경 가능한 단어
    target_li = list(target)  # 목표단어

    for i in range(l):
        dp = [0] * 26

        for word in words:
            words_li[str(list(word))] = 1
            # {"['h', 'o', 't']": 1, "['d', 'o', 't']": 1, "['d', 'o', 'g']": 1,
            # "['l', 'o', 't']": 1, "['l', 'o', 'g']": 1, "['c', 'o', 'g']": 1}

            if dp[ord(word[i]) - 97] == 0:
                dp[ord(word[i]) - 97] = 1
                alpha[i].append(word[i])  # [['h', 'd', 'l', 'c'], ['o'], ['t', 'g']]

    # BFS 구현
    queue = deque([[list(begin), 0]])  # [단어, 트리 깊이]
    check = {str(list(begin)): 1}  # 이미 시도해 본 단어

    while queue:
        string = queue.popleft()

        for i in range(l):
            for j in range(len(alpha[i])):
                tmp_string = [s for s in string[0]]  # 단어 복사 (주소값 문제로 인해)
                tmp_string[i] = alpha[i][j]  # 단어 변경

                if not check.get(str(tmp_string), 0) and words_li.get(str(tmp_string), 0):
                    if tmp_string == target_li:
                        return string[1] + 1

                    else:
                        queue.append([tmp_string, string[1] + 1])
                        check[str(tmp_string)] = 1
    return 0


print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))

 

 

'변환했던 단어는 다시 변환하지 않는다.' 이 부분을 if 현재단어 in [변환했던 단어들] 로 확인하는 게 싫었다. (계속 O(N)이 걸리니까.)

그래서 문자열과 딕셔너리를 이용했다.,

딕셔너리의 key 값으로, 단어 리스트를 문자열로 변환해서 넣었다. 그리고 value값을 1로 바꿨다.

이제 key값에 해당하는 value 값이 1일 경우 변환했던 단어임을 알 수 있다.

 

몇 단계인지 구해야 하는데, 이것은 트리의 깊이로 구했다.