bfs
1. begin이 target 이되는 최소 단계수이므로 bfs
def bfs(begin, target, words):
queue = [(begin, 0)] // 현재 단어와 , 단계를 큐에담기
while queue:
now, step = queue.pop(0)
if now == target:
return step
for word in words:
cnt = 0
for i in range(len(now)):
if word[i] == now[i]:
cnt += 1
if cnt == len(now)-1 : // 최소 알파벳 하나만 변해야 하므로
queue.append([word,step+1])
def solution(begin, target, words):
if target not in words: // target 단어가 words에 없으면 0반환
return 0
return bfs(begin, target, words)
begin = "hit"
target = "cog"
words = ["hot", "dot", "dog", "lot", "log", "cog"]
print(solution(begin,target,words))
