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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

풀이

BFS를 사용한 풀이이다. 풀고 나니 원래 보통 BFS라고 할 때 사용하는 while과 deque를 사용한 구조로 풀이되진 않았으나.. 어찌 됐든 한 단계씩 진행되는 BFS 구조를 사용하여 문제 풀이를 진행했다.

 

문제에 적힌 대로 주어진 단어의 한 글자씩 변환하며, 변환된 단어가 words 배열에 있는지 체크하고, 또 동시에 이전에 이미 변환을 진행했던 단어가 아닌지 확인하였다. 확인을 통과한 새로운 단어들을 모아 새로운 단계에서 같은 작업을 반복하는 BFS를 사용하여 풀이를 진행하였다.

def solution(begin, target, words):
    if target not in words: # 만약 target이 words 안에 없다면
        return 0 # 애초에 변환할 수 없는 경우
    
    ord_a = ord('a') # a의 유니코드 값
    ord_z = ord('z') # z의 유니코드 값
    MAX_DEPTH = 51 # words의 갯수가 50개이므로 51 단계를 초과할 수가 없음
    answer = MAX_DEPTH # 초기값 설정
    
    
    visited = [begin] # 이미 지나온 단어는 중복해서 처리하지 않게 하기 위함 
    
    
    def bfs(_words, depth): # BFS 함수
        nonlocal answer
        
        cands = set() # 현재 단계에서 시작 단어를 사용해 한 단계 변환하여 나올 수 있는 단어들을 저장할 set
        
        for word in _words: # 현재 단계의 모든 시작 단어들을 순회하며
            for i in range(len(word)): # 한 글자씩
                for j in range(ord_a, ord_z): # a~z로 대체하며
                    cand = word[:i] + chr(j) + word[i+1:] # 대체된 단어가
                    if cand == target: # target과 같다면
                        answer = depth # 현재 단계가 최소 단계임
                        return # BFS 종료

                    if cand in words and cand not in visited: # 대체된 단어가 words 배열 안에 있고, 아직 거치지 않은 단어라면
                        cands.add(cand) # cands에 저장

        return bfs(cands, depth + 1) # 한 단계 변환한 모든 단어들을 사용하여 다음 단계 진행
    
    bfs(set([begin]), 1) # BFS 진행
    
    if answer == MAX_DEPTH: # answer의 값이 초기값과 동일하다면
        return 0 # 변환할 수 없는 경우이므로 0을 반환

    return answer # BFS이므로 항상 최솟값이 찾아짐