[프로그래머스] lv3 단어 변환 / 파이썬, 고득점kit

begin에서 시작해서 target까지 단어로 변환하는데 한번에 하나의 글자만 바꿀 수 있다.
처음 문제를 읽고  이게 어떻게 그래프이론 문제지라고 생각했다. bfs의 풀이법을 떠올리면서 어떻게든 문제에 적용하려고 노력했던 문제다.
몇번만에 최소 횟수로 target에 도달할 수 있는지를 묻는 문제이기 때문에 visited를 이용해서 풀어야 한다고 생각했다.
주의점!!

• 한번에 하나의 글자만 바꿀 수 있다.
• begin과 target은 글자의 길이가 같다.
• target은 항상 words에 들어있다.
• 변환할 수 없는 경우 0을 반환한다.

 

from collections import deque
def bfs(begin, target, words, visited):
    q = deque()
    q.append([begin, 0])
    while q:
        now, cnt = q.popleft()
        if now == target:
            return cnt
        for i in range(len(words)):
            tmp_cnt = 0
            if visited[i] == 0:
                for j in range(len(now)):
                    if words[i][j] != now[j]:
                        tmp_cnt += 1
                if tmp_cnt == 1:
                    q.append([words[i] , cnt+1])
                    visited[i] = 1
    return 0

def solution(begin, target, words):
    visited = [0] * (len(words))
    return bfs(begin, target, words, visited)

 
q에 원소를 넣을 때 최소 이동 횟수인 cnt를 같이 넣어준다. visited의 값에 넣어주는 것과는 다른 방식이다. 한번에 하나의 글자만 변경할 수 있는 것을 tmp_cnt를 만들어 구현해주었다.