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

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
   
   
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1의 풀이]

---

 

문제 설명

 

 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

 

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", "target"가 "cog", "words"가

["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

 

 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0을 return 합니다.

 

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

알고리즘 분석

 

• 나의 풀이

# 재귀함수로 풀이 
def func(begin, target, words, count):
    if begin == target:  # begin과 target이 일치하면 
        return [count]  # 몇 번째 횟수인지 반환 
    answer, q, new_word = [], [], []  # count의 집합, 다음 문자열 후보, 다음 문자열 후보의 words
    for idx, word in enumerate(words):
        diff = 0  # 다른 문자의 개수 
        for i, j in zip(begin, word):
            if i != j:  # 각 문자가 다르면 
                diff += 1
        if diff == 1:  # 두 문자열의 다른 문자가 1개일 때 
            q.append(word)  # q에 현재 단어를 추가 
            new_word.append(words[:idx]+words[idx+1:]) # new_word에 words에서 word를 제외한 리스트를 추가
    if not q: # q가 비었다면 
        return []

    for a, b in zip(q, new_word):
        answer += func(a, target, b, count + 1)  # 재귀함수 

    return answer

def solution(begin, target, words):
    answer = func(begin, target, words, 0)
    if answer:  # answer에 요소가 있다면 
        return min(answer)  # answer 중에 가장 작은 값을 리턴
    return 0

 

 

• Most1의 풀이

from collections import deque

def get_adjacent(current, words):
    for word in words:
        count = 0 # 두 문자열의 다른문자 개수
        for c, w in zip(current, word):
            if c != w: # 두 문자가 다르면 
                count += 1

        if count == 1: # 두 문자열의 다른문자가 1개라면 
            yield word  # 다음 반복의 next_word를 word로 대체한다. 

def solution(begin, target, words):
    dist = {begin: 0}
    queue = deque([begin])
    
    while queue: # queue에 요소가 남아있다면 반복
        current = queue.popleft() # queue의 왼쪽 요소를 pop 

        for next_word in get_adjacent(current, words): # 함수와 yield를 이용한 반복 
            if next_word not in dist:  # dist안에 next_word가 없다면
                dist[next_word] = dist[current] + 1 
                queue.append(next_word) # next_word를 queue에 추가 
                
    return dist.get(target, 0)

 

정말 군더더기 없는 완벽한 코드인 것 같습니다.

yield를 이용한 for문 사용으로 불필요한 과정을 전부 생략해 버렸습니다. 

 

위의 코드를 간단히 설명해보겠습니다. 

solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])를 실행했다고 가정하면 

 

처음에 "queue = deque([begin])"으로 인해 "queue = deque(['hit'])"이 됩니다. 

while 문에 진입하면 

• current = 'hit' 
• for next_word in get_adjacent('hit', ["hot", "dot", "dog", "lot", "log", "cog"])

를 실행하게 됩니다.

 

여기서 중요한 것은 get_adjacent() 함수의 결과입니다.

이 함수는 간단하게 설명하자면 current와 words를 비교해서 1개의 단어만 다른 words의 요소를 yield 하는 것입니다. 

여기서 yield가 실행되는 만큼 반복하며, yield한 값이 변수 next_word를 대체하게 됩니다. 

 

이번 반복에서는 "hit"과 한 글자만 다른 단어는 "hot" 밖에 없기 때문에 

next_word = "hot"으로 한 번만 반복하게 됩니다. 

 

• if next_word not in dist:   ==> dist 안에 "hot"이 없으므로 아래 코드를 실행
•    dist[next_word] = dist[current] + 1  ==> dist["hot"] = dist["hit"] + 1 
•    queue.append(next_word)  ==> queue.append("hot") 

이렇게 되어 다음 current는 "hot"이 되게 됩니다. 

 

그다음은 위의 과정과 비슷합니다. 

"hot"과 한 글자 차이나며 dist에 없는 "dot"과 "lot"이 yield를 실행하여 

next_word에 "dot"과 "lot"이 차례대로 들어가서 반복하게 됩니다. 

 

 

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