[Programmers] 프로그래머스 단어 변환 Python

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

프로그래머스

 

❗풀이 방법

1. 백트래킹으로 한 단어씩 비교한다.

2. 현재 단어와 타겟 단어가 1자리만 다른지 can_change 함수로 판별한다.

3. 가능하다면 다음 단계로 넘어간다

4. 현재 단어가 최종 단어와 동일하다면 result를 dep와 비교하여 최솟값으로 업데이트한다

 

 

❗코드

def solution(begin, target, words):
    result = 10000
    visited = [0 for _ in range(len(words))]

    def can_change(now, word):
        differ = 0
        j = 0

        while j < len(now):
            if word[j] != now[j]:
                differ += 1
            j += 1
            
        if differ == 1:
            return True
        else:
            return False


    def backtrack(dep, now):
        nonlocal result

        if target not in words:
            result = 0
            return

        if now == target:
            result = min(result, dep)
            return

        for i, word in enumerate(words):
            if can_change(now, word) and not visited[i]:
                answer.append(word)
                visited[i] = 1
                backtrack(dep + 1, word)
                visited[i] = 0
                answer.pop()


    backtrack(0, begin)
    
    return result

 

from collections import deque

def solution(begin, target, words):
    
    # 타겟이 워드 안에 존재하지 않는 경우
    if target not in words:
        return 0
    
    def change(word1, word2):
        possible = 0
        
        if len(word1) != len(word2):
            return False
        
        for a, b in zip(word1, word2):
            # print(a, b, possible)
            if a != b:
                possible += 1
        
        if possible == 1:
            return True
        else:
            return False
        
    
    visited = [0 for _ in range(len(words))]
    max_dep = len(words)
    answer = 0
    
    temp = []

    
    def bfs(start, dep):
        nonlocal begin, target, answer
        
        # start와 타겟이 같으면 종료
        if start == target:
            answer = dep
            return
        
        # start가 최하위까지 내려가도 종료
        if start == max_dep:
            return

        for i, word in enumerate(words):
            if visited[i] == 1:
                continue
    
            if change(start, word):
                visited[i] = 1
                bfs(word, dep+1)
                visited[i] = 0

            
    bfs(begin, 0)
        
        
    return answer