프로그래머스 Level 3 단어 변환

begin에서 target으로 가는 최단경로의 길이를 찾는 문제이다.

두 단어의 차이가 한 글자면 이동 가능하다. 이동 가능한지 판별하는 부분은 아래의 조건문같이 구현했다.

if len([1 for i in range(N) if node[i] != n[i]]) != 1:

 

dfs를 사용해서 이동 가능한 모든 경로를 다 돌아보고 현재 node가 target이라면

res리스트에 지나왔던 경로의 길이를 append해준다. 마지막에 min(res)를 반환해주면 끝이다.

def solution(begin, target, words):
    def dfs(cnt, node, li, route):
        if node == target:
            res.append(cnt)
        for i, n in enumerate(li):
            if len([1 for i in range(N) if node[i] != n[i]]) != 1:
                continue
            li.pop(i)
            dfs(cnt+1, n, li, route+[n])
            li.insert(i, n)
            
    if target not in words:
        return 0
    
    N = len(begin)
    res = []
    dfs(0, begin, words, [begin])
    
    return min(res) if res else 0