프로그래머스 Lv. 3 단어 변환 Python

문제 링크

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

프로그래머스

정답 코드

from collections import deque 
def solution(begin, target, words):
    lenWords = len(words)
    lenW = len(begin)
    V = [0 for _ in range(lenWords+1)]
    q = deque()
    q.append((begin, lenWords))
    result = 1e9
    isFound = False
    while q:
        currentWord, currentIdx = q.popleft()
        if currentWord == target:
            isFound = True
            if result > V[currentIdx]:
                result = V[currentIdx]
            continue
        for nextIdx in range(lenWords):
            if nextIdx == currentIdx:
                continue
            word = words[nextIdx]
            cnt = 0
            for j in range(lenW):
                if currentWord[j] != word[j]:
                    cnt += 1
            # 하나만 다르므로 바꾼다.
            if cnt == 1:
                # 하지만 이미 방문한 단어이면
                if V[nextIdx]:
                    # 다음 가는 위치보다 현재 길이가 짧은지 비교
                    if V[nextIdx] > V[currentIdx] + 1:
                        V[nextIdx] = V[currentIdx] + 1
                        q.append((words[nextIdx], nextIdx))
                else:
                    V[nextIdx] = V[currentIdx] + 1
                    q.append((words[nextIdx], nextIdx))

    if isFound:
        print(V)
        return result
    return 0

풀이 방법

- 현재 단어를 거쳐 갔는지 확인 하기 위해 방문 배열을 만든다.

- 현재 단어가 target인지 확인한다.

    - 현재 단어가 target이면 지금의 길이가 제일 짧은지 비교하고 값을 result에 넣는다.

- 현재 index가 다음 index와 같으면 같은 단어라는 의미이므로 continue

- 현재 단어와 다음 단어를 비교해서 알파벳이 하나만 다른지 확인한다.

- 하나만 다른 다음 단어를 가지고

    - 다음 단어가 이미 방문했다면 방문 배열의 값과 이제 방문할 값 V[currentIdx] + 1과 비교한다.

    - 작으면 다시 순환시킨다.

- 방문 안 한 단어는 당연히 순환시킨다.

- 마지막으로 target을 찾았을 때는 isFound가 true 이므로 result값을 출력

- 찾지 못한 경우 0을 출력한다.

느낀점

- 이정도는 이제 쉽게 풀 수 있어야 한다.