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

 

 

나의 풀이

from collections import deque

def check(w1, w2):
    count = 0

    for l1, l2 in zip(w1, w2):
        if l1 != l2:
            count += 1

    if count == 1:
        return True
    else:
        return False


def solution(begin, target, words):
    if target in words:
        visited = []
        queue = deque([(begin,0)])

        while queue:
            w, c = queue.popleft()
            if w == target:
                return c
            if w not in visited:
                visited.append(w)
                for x in words:
                    if x not in visited and check(w, x):
                        queue.append((x , c + 1))

    return 0

 

 

DFS를 활용한 풀이

answer = 0
def solution(begin, target, words):

    dfs(begin, target, 0, words)
    return answer

def change(fr, to):
    for i in range(len(fr)):
        if fr[:i]+fr[i+1:] == to[:i]+to[i+1:]:
            return True
    return False

def dfs(begin, target, d, words):
    global answer
    # print(begin)
    # print(words)
    if begin == target:
        # print(d)
        answer = d
        return
    else:
        if len(words) == 0:
            return 
        for w in range(len(words)):
            if change(begin, words[w]):
                word = words[:w]+words[w+1:]
                dfs(words[w], target, d+1, word)