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

3️⃣ 단어 변환

문제 설명

두 개의 단어 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

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

💡 아이디어

예시들을 보면 target이 words에 있어야한다.

처음에는 조금 단순하게 생각하고 풀었다.

단어중에 하나만 다르면 바꿔주는 식으로 풀었다.

그러나 문제점은 가장 짧은 변환 횟수를 찾지 못함 + target을 고려하지 못함

역시나 이를 위해서는 queue를 사용한 BFS풀이법을 적용해야했다.

틀린 풀이

from collections import deque

def solution(begin, target, words):
    ans = 0
    
    if target in words: #target이 words에 있을 경우
        for word in words: # 각 단어 
            count = 0
            for w in word: # 각 단어의 알파벳 
                print("words의 알파벳", w) #알파벳
                if w in begin:
                    print("begin의 알파벳", w) # 단어의 알파벳
                else: 
                    count += 1
            if count == 1:  
                print("변환할 알파벳", word)
                begin = word
                ans += 1
                print(begin)
        return ans

    else:
        return ans

📝 정답 풀이

from collections import deque

def solution(begin, target, words):    
    if target in words: #target이 words에 있을 경우
        q = deque()
        q.append([begin, 0]) #시작단어, 카운트
        
        while q:
            b, cnt = q.popleft() #시작단어와 카운트 pop
            if b == target: #시작 단어가 타겟과 같으면
                return cnt #카운트 반환
            for i in range(0, len(words)):
                diff = 0 # 다른거 찾기
                word = words[i] # 한 단어씩
                for j in range(len(b)): #시작단어의 알파벳 하나씩 
                    if b[j] != word[j]: #한 단어의 알파벳 하나씩 
                        diff += 1
                if diff == 1: #다른 알파벳이 하나라면 
                    q.append([words[i], cnt+1]) #큐에 다시 넣어준다
        return cnt
        
    else:
        return 0

❗ 느낀점

깊게 생각하고 조건 하나하나 살펴보자