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

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

우선 내가 작성한 코드와 그에 대한 테스트 점수는 아래와 같다.

from collections import deque

def solution(begin, target, words):
    answer = 0
    # 애초에 후보에 정답이 없는 경우
    if target not in words:
        return 0
    # bfs 방식
    q = deque([begin])
    while q:
        v = q.popleft()
        if v == target:
            return answer
        for word in words:
            if len(set(v) - set(word)) == 1:
                print(len(set(v) - set(word)), v, word)
                q.append(words.pop(words.index(word)))
                answer += 1
                break

bfs 방식으로 풀이를 했는데, 주어진 단어를 모두 방문해야했기 때문이다.

보통은 왜 80점을 받는지 납득할 수 없는 경우가 많은데, 이번엔 내가 왜 80점을 받는 지 안다.
아마 더 많은 테스트 케이스가 있었다면 더 낮은 점수를 받았을 것이다.

우선 해당 문제는 최소의 경우를 구해야한다.

위의 예제는 최소의 횟수가 4번이 나온다.
하지만 내가 작성한 코드대로 동작을 시키면 5번의 횟수가 출력된다.
이유는 최소의 횟수를 구하지 않기 때문이다.
단어가 저장된 순서대로 순회하기 때문에 최소의 횟수가 출력되지 않는 것이다.

"hit" -> "hot" -> "dot" -> "dog" -> "log" -> "cog"

"dog"에서 "cog"로 바로 가지 않고 "log"를 거쳐간다.
이유는 저장된 단어 순으로 조회하면서, 단어에서 알파벳의 개수 차이가 1이면 해당 단어로 바꾸기 때문이다.

끝내 최소의 횟수를 구하는 방식을 떠올리지 못해 구글링을 하여 정답을 참고하였다.

from collections import deque


def solution(begin, target, words):
    answer = 0
    q = deque()
    q.append([begin, 0])
    V = [ 0 for i in range(len(words))]
    while q:
        word, cnt = q.popleft()
        if word == target:
            answer = cnt
            break        
        for i in range(len(words)):
            temp_cnt = 0
            if not V[i]:
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        temp_cnt += 1
                if temp_cnt == 1:
                    q.append([words[i], cnt+1])
                    V[i] = 1
                    
    return answer