[프로그래머스/파이썬] DFS/BFS 단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163

---

알고리즘 분류

• BFS

문제풀이

graph딕셔너리에 begin부터시작해서 words의 단어별까지 몇단계의 과정을 거치는 지 카운트한 값을 저장한다.

ex)
now="hit, word="hot","dot","dog"...
zip함수부분은 단어차이 횟수를 저장해준다.

{'hot': 1, 'dot': 0, 'dog': 0, 'lot': 0, 'log': 0, 'cog': 0, 'hit': 0}
{'hot': 1, 'dot': 2, 'dog': 0, 'lot': 0, 'log': 0, 'cog': 0, 'hit': 0}
{'hot': 1, 'dot': 2, 'dog': 0, 'lot': 2, 'log': 0, 'cog': 0, 'hit': 0}
{'hot': 1, 'dot': 2, 'dog': 3, 'lot': 2, 'log': 0, 'cog': 0, 'hit': 0}
{'hot': 1, 'dot': 2, 'dog': 3, 'lot': 2, 'log': 3, 'cog': 0, 'hit': 0}
{'hot': 1, 'dot': 2, 'dog': 3, 'lot': 2, 'log': 3, 'cog': 4, 'hit': 0}

소스코드

def solution(begin, target, words):
    from collections import deque
    
    graph={i:0 for i in words}
    graph[begin]=0
    
    queue=deque()
    queue.append(begin)
    
    while queue:
        now=queue.popleft()
        if now==target:
            break
        for word in words:
            cnt=0
            for a,b in zip(now,word):
                if a==b:
                    cnt+=1
            if cnt==len(word)-1 and graph[word]==0:
                graph[word]=graph[now]+1
                queue.append(word)
    
    if target in words:
        return graph[target]
    else:
        return 0