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

깊이/너비 우선 탐색 (DFS/BFS)

🌏 문제

프로그래머스

 

👽 풀이 ➡️ DFS 이용

💫 문제 분석

문제에서 한 번에 한 개의 알파벳만 바꿀 수 있다고 주어져서 

처음에 len(set(w1) - set(w2)) == 1 이렇게 접근했는데

이 경우에 'aaa'와 'aab'를 비교하게 되면 0이 나오기 때문에 테스트케이스 3번에서 실패가 뜬다😢

 

그래서 두 문자를 비교하는 함수를 따로 만들어줬다.

    def compare(w1, w2):
        diff = 0
        for i in range(len(w1)):
            if w1[i] == w2[i]:
                continue
            else:
                diff += 1
                if diff > 1:
                    return False
        
        if diff == 1:
            return True
        
        return False

 

💫 최종 코드

def solution(begin, target, words):
    global answer
    answer = 0
    dic = {word : 0 for word in words}
    
    def compare(w1, w2):
        diff = 0
        for i in range(len(w1)):
            if w1[i] == w2[i]:
                continue
            else:
                diff += 1
                if diff > 1:
                    return False
        
        if diff == 1:
            return True
        
        return False
    
    def dfs(word, idx):
        global answer
        
        if idx > len(words):
            return
            
        if word == target:
            if answer == 0:
                answer = idx
            else:
                answer = min(answer, idx)
        
        for i in words:
            if compare(i, word) and dic[i] == 0:
                dic[i] = 1
                dfs(i, idx + 1)
                dic[i] = 0

    dfs(begin, 0)
    
    
    return answer