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

문제

 

 

이 문제는 주어진 단어를 한개의 알파벳만 변환해주면서 target이라는 단어와 같도록 변환을 해주는데 이때 변환을 하는데 필요한 "최소" 단계 수를 구해주는 문제이다.

 

최소 단계를 구하는 문제이기때문에 bfs를 사용하여 문제를 풀어주었다.

 

이때 queue 를 사용해서 문제를 풀어주는데 queue에 다음에 들어갈 단어와 단계까지 같이 넣어주면 된다.

 

나의 코드

from collections import deque
def solution(begin, target, words):
    answer = 0
    #변환할 수 없는 경우
    if target not in words:
        return answer
    
    return bfs(begin, target, words)
    
def bfs(begin, target, words):
    
        q = deque()
        #첫번째 단계는 0으로 초기화
        q.append([begin,0])
        
        while(q):
            now, step = q.popleft()
            #target과 같아지면 종료
            if now == target:
                return step
            
            for word in words:
                #다른 알파벳의 개수를 세주는 cnt
                cnt = 0
                for i in range(len(word)):
                    if word[i] != now[i]:
                        cnt += 1
                #알파벳이 하나만 다르다면 q에 추가해주고 단계를 +1하여 추가해줌        
                if cnt == 1:
                    q.append([word,step+1])

 

 

평소에 자주 풀던 bfs 형태의 문제에서 queue에 인자값을 하나 더 해주어 step이라는 단계를 기록하는 인자값을 추가해주는 것을 생각해내는 부분이 가장 까다로웠던 문제였던 것 같다.

 

bfs 문제를 풀 때 문제에 주어진 조건에 맞게 형태를 변경해주는 방법에 대해서 배우게 된 문제이다.