[programmers] 단어 변환 python

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

문제

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
   예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

풀이과정

• target이 words에 없으면 0을 리턴한다.
• 한번에 하나의 알파벳만 변경 가능하므로, 알파벳의 인덱스에 따라 비교한다. ex. abc와 abd는 가능, abc와 acb는 불가능 (2글자 변경)
• visit배열을 이전 값 + 1로 업데이트하여 최종 target에 도달했을 때, target의 visit 값을 리턴한다.

소스코드

소요 시간 39:30

def bfs(begin, target, words):
    q = [begin]
    visit = [0] * len(words)
    index = words.index(target)
    while q:
        text = q.pop(0)
        if text == target:
            return visit[index]

        for i in range(1, len(words)):
            sum_of_word = 0
            if not visit[i]:
                for a, b in zip(text, words[i]):
                    if a == b:
                        sum_of_word += 1
                if sum_of_word == len(text) - 1:
                    visit[i] = visit[words.index(text)] + 1
                    q.append(words[i])
    return 0



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

    # target이 words안에 존재하지 않으면
    if target not in words:
        return 0

    words.insert(0,begin)
    answer = bfs(begin, target, words)
    return answer