깊이/너비 우선 탐색(DFS/BFS)-단어 변환*

from collections import deque

def solution(begin, target, words):

    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()

        next_words = []

        for i in words:
            diff = 0 
            for j in range(len(begin)) :
                if i[j] != current[j]:
                    diff += 1 
            
            if diff == 1 : 
                next_words.append(i)

        for next_word in next_words:
            if next_word not in dist:
                dist[next_word] = dist[current] + 1
                queue.append(next_word)

    return dist.get(target, 0)

 

1. 분류 : BFS 

2. 풀이 방법 

 

step 1) bfs 알고리즘을 구현하기 위하여 deque 를 사용한다. 

step 2 ) dist = { 단어 : 변환한 수 } 를 표현하는 딕셔너리 이다.  처음에 begin 을 넣고 deque 에도 begin 을 넣는다. 

step 3 ) current 는 지금 검증할 단어이다. 

           -> 만약 current 와 알파벳 1개 차이가 나는 단어가 있다면 next_words 배열에 넣는다.

step 4 ) next_words 가 전에 바뀌었던 단어가 아니라면, dist 와 queue 에 넣어 준다. 

 

=> 4 단계 까지 오게 되면 모든 단어 변환을 거친다. 

 

step 5 ) 만약 dist 에 target 이 있다면 ( 변환 가능함을 의미 ) 변환 한 수를 출력하고, 없다면 0 ( default ) 를 출력한다. 

 

 

+ tip )  딕셔너리의 get method 

 

딕셔너리.get( key[ , defualt 값 ] ) 

: 딕셔너리에 key 가 있으면 해당 key의 value를 반환하고, 없으면 default에 지정한 값을 반환한다. 

default 생략 시, 아무런 값도 ( None ) 반환하지 않는다.