[프로그래머스]단어 변환 - DFS/BFS

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

코딩테스트 연습 - 단어 변환

 

BFS 알고리즘 이용

from collections import deque


def solution(begin, target, words):
    queue = deque()
    length = len(words)
    word_length = len(begin)
    
    # 단어를 변환할 수 있는지 여부를 체크하는 함수
    def can_change(word, change):
        diff = 0
        for i in range(word_length):
            if word[i] != change[i]:
                diff += 1
        if diff == 1:
            return True
        else:
            return False
    
    def bfs():    
        queue.append([begin, 0])

        # 변환할 수 없는 경우
        if target not in words:
            return 0
        
        while queue:
            word, depth = queue.popleft()
            
            if word == target:
                return depth
            
            # words 목록을 순회하며, 변경 가능한 경우에 큐에 추가.
            # 가장 빨리 target이 되는 경우가 최소 변환과정임 (BFS의 특징)
            for change in words:
                if can_change(word, change):
                    queue.append([change, depth+1])

    answer = bfs()
    return answer

 

코드 설명

can_change : 단어를 변환할 수 있는지 여부를 체크하는 함수

 

bfs :

1. bfs 함수에서 초기값을(begin, depth=0) 큐에 넣어줍니다.
2. 만약 변환할 수 없는 경우라면 0을 return 합니다.
3. 큐가 존재할 때까지 반복합니다.
   1. 큐에서 word, depth를 빼옵니다.
   2. words 목록을 순회하면서 변경이 가능한 경우라면 큐에 추가합니다.
   3. 이 때, 가장 빨리 target이 되는 경우가 최소 변환 과정을 의미합니다. (depth를 return)

 

Point : BFS 알고리즘의 경우 주로 "최소"를 찾는데 사용됩니다. 해당 문제의 경우 최소 변환 과정을 찾는 것이기에 bfs를 이용하였습니다. 따라서 BFS 특징을 이용해 가장 빠르게 target이 되는 경우가 가장 최소의 변환 과정입니다.