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

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

프로그래머스

 

내 코드

from collections import deque

def solution(begin, target, words):
    if target not in words:
        return 0
    
    q = deque()
    q.append([begin, 0])

    while q:
        tmp, cnt =q.popleft()
        
        if tmp ==target: #같으면 cnt 반환
            return cnt
        
        for i in range(len(words)): #word리스트 기준으로 돌리는데
            chk = 0 #검사 변수 리셋해주고
            word = words[i] #처음 단어를 word 변수에 넣어줌
            
            for j in range(len(tmp)):  #현재 저장된 단어(바로 직전에 검사한 단어의 길이만큼)
                if tmp[j] != word[j]: #단어 검사
                    chk +=1 #단어 틀리면 1씩 증가
            if chk == 1: #만약 1개만 틀렸으면
                q.append([word, cnt+1]) #[단어, cnt+1] 이 자체를 q에 넣어줌
    return 0 #위에서 cnt로 반환하니까 상관없음

 

BFS, 변수 활용해서 검사하기

처음에 문제를 보자마자 너무 막막했다. 단어를 하나하나 검사하고, 어떻게 바꾸지라는 생각뿐이었다. 

그래서 구글링을 좀 했는데, 웬걸 단어를 바꾸는 것이 아니라 그냥 리스트 안의 단어들을 확인만 하고 cnt만 늘려가면 되는 것이었다.

여기서 중요한 것은 chk 라는 함수와 q에 리스트 자체를 넣어버리는 것이다.

특히 q.append([begin, 0]) 해서 q.popleft()로 꺼내면서 변수 값을 계속 수정해준다.

q에 변수값 두 개를 한꺼번에 넣는 것이 너무 좋은 것 같다.