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

BFS

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

 

문제가 발생한 점

처음에 visited 를 체크하지 않아서 시간 초과 발생

> 한번 방문한 words 를 체크하지 않도록 해줘야 한다 : 최소값을 탐색하기 때문

 

어려웠던 점

문자열이 하나만 제외하고 모두 같은 경우를 어떻게 해야할지 감이 안왔음

모든 문자열의 갯수가 같다는 점을 이용하여 count 해서 다른 문자의 갯수가 1인 경우로 체크함