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

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

 

-접근법

이 단어들이 그래프로 연결되어 있다고 가정했을때, 한번의 변환으로 같은 단어가 될 수 있는 두 단어의 관계는 연결되어있다고 볼 수 있을 이다. 따라서 begin을 시작점으로 다음으로 갈 수 있는 단어들을 찾아서 각각 탐색하며, 그 단어로부터 갈 수 있는 다음 단어들을 순차적으로 찾아가는 BFS방식으로 탐색을 하다가 target word가 나오면 몇번째 탐색에 word를 찾았는지 반환하면 될 것 입니다.

def getNext(cur_word, isvisit,words):
    result =[]
    word_len = len(cur_word)
    for w in words:
        if w not in isvisit and sum( 1 if cur_word[i] != w[i] else 0 for i in range(word_len) ) == 1:
            isvisit.add(w)
            result.append(w)
    return result

def solution(begin, target, words):
    isvisit= set()
    cur_q = getNext(begin,isvisit, words)
    prev_q =[]
    level = 1
    while cur_q :
        prev_q = cur_q
        cur_q = []
        for p in prev_q :
            if p==target :
                return level
            cur_q +=getNext(p, isvisit,words)
        level +=1
    return 0