[프로그래머스/Python] - Lv3 / 단어 변환

level3 - BFS(최단거리) - 단어변환

😀 이 문제는 처음에 BFS로 풀어야겠다는 것을 알면서도 그 행위를 쉽게 시도하지 못했다. 왜냐하면 BFS겠구나 생각은 해도 어떻게 코드로 구현할지는 내 능력인데.. 아직은 많이 부족하다. 현재 단어와 현재 단어까지 도달하는데 걸린 카운트를 같이 매개변수로 줘서 구하는 것이 베스트였다.

• 문제를 해석하는 능력을 높이는 것이 중요하겠다.

from collections import deque
def solution(begin, target, words):
    if target not in words:
        return 0 #바로 끝내기
    
    n = len(words)
    ch = [0] * n
    res = 0
    def BFS():
        dq = deque()#해당 단어를 만드는데 몇번 걸렸는지를 확인하는 카운트도 함께.
        dq.append((begin, 0))
        
        while dq:
            word, cnt = dq.popleft()
            if word == target:
                return cnt
            #그게 아니라면 계속 찾아나가야함(상태트리)
            for i in range(n): #단어 개수만큼
                if ch[i] == 0: #아직 확인 안한 단어
                    temp = words[i]
                    m = len(temp)
                    count = 0
                    for j in range(m):
                        if word[j] != temp[j]:
                            count += 1
                    if count == 1: #한글자만 다른 경우 뻗어나갈 수 있음
                        dq.append((temp, cnt + 1))
                        ch[i] = 1 #넣을꺼니까 갱신
        return 0
    res = BFS()
    return res

코멘트

해당 문제는 글자가 단 하나만 다를 때 words 안에 있는 다른 단어로 바꿀 수 있다는.. 즉 상태트리로 뻗어나갈 수 있다는 걸 파악할 수 있었어야 했다. 그렇기에 단어를 하나씩 꺼내면서 그와 함께 저장된 cnt에서 만약 결과값 target 단어로 뻗어갈 수 있다면 발견한 것이고. 가장 빨리 발견한 것이 최소 횟수가 되므로 그게 정답이야.