[프로그래머스] Level 3 : 단어 변환 (Python)

[프로그래머스]  Level 3 :  단어 변환 (Python)

 

목차

 

 

 

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

프로그래머스

코드 링크

https://github.com/stellaluminary/Programmers

GitHub - stellaluminary/Programmers

 

 

Python

 

방법 1 

 

DFS를 통한 백트래킹으로 문제 해결

 

def diff_check(a, b):
    l = 0
    for i in range(len(a)):
        if a[i] == b[i]:
            l += 1
    if l == len(a) - 1:
        return True
    else:
        return False


def dfs(current, target, words, visit, depth, ans):
    if current == target:
        ans.append(depth)
        return

    for i in range(len(words)):
        if not visit[i]:
            if diff_check(current, words[i]):
                visit[i] = 1
                dfs(words[i], target, words, visit, depth + 1, ans)
                visit[i] = 0


def solution(begin, target, words):
    if target not in words:
        return 0

    visit = [0] * len(words)
    ans = []
    dfs(begin, target, words, visit, 0, ans)
    if ans:
        return min(ans)
    else:
        return 0

 

방법 2 

 

BFS를 통한 방법으로 해결

 

from collections import deque

def solution(begin, target, words):
    if target not in words:
        return 0

    q = deque()
    q.append([begin, 0])
    v = [0] * len(words)

    while q:
        word, cnt = q.popleft()
        if word == target:
            return cnt
        for i in range(len(words)):
            diff = 0
            if not v[i]:
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        diff += 1
                if diff == 1:
                    v[i] = 1
                    q.append([words[i], cnt + 1])
    return 0