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

고급

from collections import deque as queue

transistable = lambda a,b: sum((1 if x!=y else 0) for x,y in zip(a,b)) == 1

def solution(begin,target,words):
    q, d = queue(), dict()
    q.append((begin, 0))
    d[begin] = set(filter(lambda x:transistable(x,begin), words))
    
    for w in words:
        d[w] = set(filter(lambda x:transistable(x,w), words))
       
    while q:
        cur, level  = q.popleft()
        if level > len(words):
            return 0
        for w in d[cur]:
            if w == target:
                return level + 1
            else:
                q.append((w, level + 1))
    
    return 0

출처: cocojelly.github.io/algorithm/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%97%B0%EC%8A%B5-DFS-BFS-(2)/ 

 

다른 풀이(실전에서는 이런식으로 풀 수 밖에 없을 듯)

from collections import deque


def get_adjacent(current, words):
    for word in words:
        if len(current) != len(word):
            continue

        count = 0
        for c, w in zip(current, word):
            if c != w:
                count += 1

        if count == 1:
            yield word


def solution(begin, target, words):
    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()

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

    return dist.get(target, 0)
    
# output of dist
# {'hit': 0, 'hot': 1, 'dot': 2, 'lot': 2, 'dog': 3, 'log': 3, 'cog': 4}

get_adjacent 함수로 인접 element인지 확인후 해당 word를 return

인접 element인 next_word가 dist 딕셔너리에 없다면 거리를 +1해주면서 딕셔너리에 추가하고 queue에도 next_word를 추가

 

이런식으로 dictionary를 채우면 target까지의 거리가 target의 value값으로 저장

 

마지막라인에 get을 사용해서 target값에 해당하는 key가 존재하지 않을 경우 0을 return 하도록 함

딕셔너리 안에 찾으려는 Key 값이 없을 경우 미리 정해 둔 디폴트 값을 대신 가져오게 하고 싶을 때에는 get(x, '디폴트 값')을 사용하면 편리하다.

>>> a.get('foo', 'bar')
'bar'

a 딕셔너리에는 'foo'에 해당하는 값이 없다. 따라서 디폴트 값인 'bar'를 돌려준다. 출처: https://wikidocs.net/16