[프로그래머스 Programmers][Python] 단어 변환

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

프로그래머스

BFS 문제다.

 

onemissing 은 일단 한글자가 다른가를 확인하는 함수이다.

그 다음 일반적인 bfs처럼, 단어를 순회하면서 한글자만 다른지 onemissing으로 확인한다.

물론 중복체크를 위해 dict v를 사용한다.

그리고 큐에 (단어, 사용 횟수)를 적고, 단어가 target이 되면 답을 반환한다.

 

 

from collections import deque

def onemissing(a,b,n):
    ret=0
    for i in range(n):
        if a[i]!=b[i]:
            ret+=1

    if ret == 1:
        return True
    else:
        return False


def solution(begin, target, words):
    answer = 0

    v = dict()
    lenwords = len(begin)
    q = deque()
    q.append((begin,0))
    v[begin] = True
    while q:

        cur,l = q.popleft()

        for w in words:
            if onemissing(w,cur,lenwords) and w not in v:
                q.append((w,l+1))
                v[w] = True
                if w==target:
                    answer = l+1
    
    return answer