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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=python3

프로그래머스

코드

from collections import deque
def solution(begin, target, words):
    visited = [False] * len(words)
    answer = 0
    q = deque()
    q.append([begin,0])
    while q:
        now,cnt = q.popleft()
        if now == target:
            answer = cnt
            break
        for i in range(len(words)):
            trans_cnt = 0
            if visited[i] == False:
                for j in range(len(now)):
                    if now[j] != words[i][j]:
                        trans_cnt += 1
                if trans_cnt == 1:
                    q.append([words[i],cnt+1])
                    visited[i] = True
    return answer

풀이

• 4방향 탐색과 다른점은 현재 단어(now)에서 words의 원소가 아직 탐색하지 않은 단어이면, for문을 통해 자릿수를 체크해야한다는 점이다.
• 현재 단어에서 다음 단어로 바꿀수 있는 조건이 1회만 변경된 경우이므로, 알파벳 단위로 체크해서 다른 횟수(trans_cnt)를 체크해서 1인경우, 변환할 수 있는 단어이므로 q에 해당 단어와 cnt+1을 넣어준다.