[프로그래머스, 파이썬] 단어 변환 - 레벨 3 | 깊이/너비 우선 탐색(DFS/BFS)

📌 프로그래머스 - 단어 변환

<내 답안>

from collections import defaultdict, deque
def solution(begin, target, words):
    answer = 0
    # words에 존재하지 않으면 0
    if target not in words:
        return 0
    # key: 단어, value = 쌓인 변환 횟수
    visit = defaultdict(int)
    visit[begin] = 0
    q = deque([[begin,0]])
    while q:
        w,cnt = q.popleft()
        if w == target:
            answer = cnt
            break
        # 다른 단어 갯수 check
        for i in range(len(words)):
            dif = 0
            for j in range(len(w)):
                if dif >= 2:
                    break
                if w[j] != words[i][j]:
                    dif += 1
            # 단어가 하나만 다르고 방문한 적 없는 단어면,
            if dif == 1 and visit[words[i]] == 0:
                visit[words[i]] = cnt+1
                q.append([words[i],cnt+1])
    return answer

bfs로 풀었다.
defaultdict이랑 deque를 사용하는 걸 좋아해서(ㅋㅋ) 자주 사용하는데, 굳이 안써도 풀릴 것 같다.

<답안 해석>

from collections import defaultdict, deque
def solution(begin, target, words):
    answer = 0
    # words에 존재하지 않으면 0 
    # => 어차피 words에 target 단어가 없으면 target에 도달할 수 없으므로.
    if target not in words:
        return 0

visit이라는 유사 dictionary에서 방문과 동시에 쌓인 변환 갯수를 담아주었다.
key = 단어(word), value = count
visit[단어] = 지금까지 변환 count

    # key: 단어, value = 쌓인 변환 횟수
    visit = defaultdict(int)
    visit[begin] = 0

    q = deque([[begin,0]])
    while q:
    	# w = 현재 다루고 있는 word, cnt = 변환 횟수
        w,cnt = q.popleft()
        # target에 도달하면 break(자동으로 최솟값 찾고 끝)
        if w == target:
            answer = cnt
            break

       # 다른 단어 갯수 check
       for i in range(len(words)):
           dif = 0
           for j in range(len(w)):
               if dif >= 2:
                   break
               if w[j] != words[i][j]:
                   dif += 1
           # 단어가 하나만 다르고 방문한 적 없는 단어면,
           if dif == 1 and visit[words[i]] == 0:
               visit[words[i]] = cnt+1
               q.append([words[i],cnt+1])
   return answer