[프로그래머스][python][너비 우선 탐색/BFS] 단어 변환 문제

프로그래머스

 

✏️ 내가 작성한 코드 - BFS

from collections import deque

def chk(word1, word2):
    cnt = 0
    
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            cnt += 1

    if cnt > 1 or cnt == 0:
        return 0
    else:
        return 1


def solution(begin, target, words):
    step = 0
    visit = [False] * len(words)
    q = deque()
    q.append([begin, 0])

    if target not in words:  # target이 words에 없으면 0 리턴
        step = 0
    else:
        while q:
            word, cnt = q.popleft()

            if word == target:
                step = cnt
                break

            for w in range(len(words)):
                if visit[w] == False and chk(words[w], word):
                    visit[w] = True
                    q.append([words[w], cnt + 1])

    return step

 

✏️ 참고

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.

위 조건을 참고하여, chk 함수를 작성하였다.

두 단어 각 알파벳을 비교하며 cnt를 증가시키고 cnt가 1인 경우에만 조건에 해당한다.