[python] 프로그래머스 단어 변환 BFS

코딩테스트 연습 - 단어 변환 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 해석

begin에서 시작한 단어기 target 단어로 변환할 때 바뀐 횟수를 구하기

- 변환할 수 있는 단어는 words 배열에 있어야하며 begin 글자에서 한 글자만 바뀌어야한다.

 

접근 방법

BFS를 사용하여 begin에서 변환할 수 있는 단어를 queue에 담아주었다.

import queue
que = queue.Queue()

def solution(begin, target, words):
    count = 0
    if target not in words:
        return count
    words = list(set(words))    #set을 사용하여 중복 제거
   
    que.put(begin)
    que.put(count)

    while(que.qsize!=0):
        begin = que.get()
        count = que.get()
        begin_list = list(begin)
        for i in range(len(words)):
            temp_list = list(words[i])  #list에 글자를 하나씩 담고 비교
            sub_cnt = 0
            for j in range (len(begin_list)):
                if(begin_list[j]!=temp_list[j]):
                    sub_cnt+=1
            if(sub_cnt==1): #만약 바뀐 글자가 하나라면
                if(words[i]==target):
                    return count + 1
                que.put(words[i])
                que.put(count+1)

    answer = count
    return answer

 

시간 복잡도

O(n^2)