단어 변환

Programmers Level 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 : "hit"
target : "cog"
words : ["cog", "hot", "dot", "dog", "lot", "log"]
>> 4

---

풀이

from collections import deque
def check_one_word(word,begin):
    counting = 0
    for w,b in zip(word,begin):
        if w != b:
            counting +=1
    return True if counting ==1 else False

def solution(begin,target,words):

    if target not in words:
        return 0
    queue = deque()
    queue.append([begin,[]])
    
    while queue:
        begin, visited = queue.popleft()
            
    	print("--------------- start ---------------")
    	print("begin, visited : ", begin, visited)
    
        for word in words:
            print('for start', word)
            if word not in visited and check_one_word(word,begin):
                if word == target:
                    return len(visited)+1
                else:
                    temp = (visited[:])
                    temp.append(word)
                    queue.append([word,temp])
                    print(queue)
        print()

begin = "hit"
target = "cog"
words = ["cog","hot", "dot", "dog", "lot", "log"]
print(solution(begin, target, words))

• queue.append([begin,[]])
  : begin = words 배열에서 비교할 기준이 될 단어!

• for word in words: : begin 을 기준으로 전체 단어 순회

• if word not in visited and check_one_word(word,begin):
  : word = 방문했던 단어가 아니면서, 기준단어와 알파벳 1개만 다른 단어라면,

  • if : target 과 같다면 return
  • else : 새로운 기준단어로 word를 추가 및 새로운 방문리스트 생성 후, append

---

• 코드 내 print 문 출력

--------------- start ---------------
begin, visited :  hit []
deque([])
deque([['hot', ['hot']]])
deque([['hot', ['hot']]])
deque([['hot', ['hot']]])
deque([['hot', ['hot']]])
deque([['hot', ['hot']]])

--------------- start ---------------
begin, visited :  hot ['hot']
deque([])
deque([])
deque([['dot', ['hot', 'dot']]])
deque([['dot', ['hot', 'dot']]])
deque([['dot', ['hot', 'dot']], ['lot', ['hot', 'lot']]])
deque([['dot', ['hot', 'dot']], ['lot', ['hot', 'lot']]])

--------------- start ---------------
begin, visited :  dot ['hot', 'dot']
deque([['lot', ['hot', 'lot']]])
deque([['lot', ['hot', 'lot']]])
deque([['lot', ['hot', 'lot']]])
deque([['lot', ['hot', 'lot']], ['dog', ['hot', 'dot', 'dog']]])
deque([['lot', ['hot', 'lot']], ['dog', ['hot', 'dot', 'dog']], ['lot', ['hot', 'dot', 'lot']]])
deque([['lot', ['hot', 'lot']], ['dog', ['hot', 'dot', 'dog']], ['lot', ['hot', 'dot', 'lot']]])

--------------- start ---------------
begin, visited :  lot ['hot', 'lot']
deque([['dog', ['hot', 'dot', 'dog']], ['lot', ['hot', 'dot', 'lot']]])
deque([['dog', ['hot', 'dot', 'dog']], ['lot', ['hot', 'dot', 'lot']]])
deque([['dog', ['hot', 'dot', 'dog']], ['lot', ['hot', 'dot', 'lot']], ['dot', ['hot', 'lot', 'dot']]])
deque([['dog', ['hot', 'dot', 'dog']], ['lot', ['hot', 'dot', 'lot']], ['dot', ['hot', 'lot', 'dot']]])
deque([['dog', ['hot', 'dot', 'dog']], ['lot', ['hot', 'dot', 'lot']], ['dot', ['hot', 'lot', 'dot']]])
deque([['dog', ['hot', 'dot', 'dog']], ['lot', ['hot', 'dot', 'lot']], ['dot', ['hot', 'lot', 'dot']], ['log', ['hot', 'lot', 'log']]])

--------------- start ---------------
begin, visited :  dog ['hot', 'dot', 'dog']
4