[프로그래머스] LEVEL3 단어 변환, python3, 깊이/너비 우선 탐색(DFS/BFS)

def solution(begin, target, words):
    if not target in words:
        return 0
        
    answer = 0
    queue = [begin]           
    while words!=[]:
        answer+=1
        tmp=[]
        while queue:
            word_stack=queue.pop(0)
            for word in words: 
                change=0
                for i in range(len(word)):
                    if word[i]==word_stack[i]:
                        change+=1
                if change==len(word)-1:
                    tmp.append(word)
        words= list([word for word in words if word not in tmp])
        #print("after:",tmp,words)
        if tmp==[] and words!=[]:
            return 0
        queue.extend(tmp)
        #print(queue,'\n')
        if target in queue:
            break

    return answer

---

어제 DFS, BFS를 공부했었기때문에 오늘은 얼추 어떻게 구현할지 감이왔었다.

우선 target이 있는지 부터 확인을해서 없으면 0이 나오게 하고 있으면 단계별로 넘어갈수있는지를 확인하였다.

예제 1 "hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"] 의 경우를 보자.

begin: hit, target: cog 
answer=1 [hot] 
answer=2 [dot, lot] 
answer=3 [dog, log] 
answer=4 [cog]  

한 층씩 내려갈때마다 한글자씩만 바뀌는 경우를 찾아야하므로 첫 층에서는 hot이 나와야한다.

두번째 층에서는 hot에서 dot과 lot을 갈수가 있고, 세번째 층에서는 dot에서 dog, lot에서 log로 간다.

두번째와 세번째를 트리로 확인하면 하나씩 연결해야하지만 계층만 확인할 것이므로 한꺼번에 넣었다.

네번째는 dog에서 cog으로 가므로 target이 네번째 층에 있는걸 알수있다.

 

이렇게 한 층씩 내려가면서 다음층을 확인해야하는 것을 생각하였기에 BFS를 사용하였고 각 층마다 target이 있는지 확인하였다.

또한 각 계층에서 내려갈수 있는 경우가 없는데 리스트words에 target이 남아있는 경우가 있을수도 있으므로 그경우에는 0을 return하게 만들었다.

 

target은 words에 있는데 내려갈수있는 계층이 없는경우