📖 문제

📝 풀이 과정

1. 리스트 words 내에 target 단어가 없으면 변환할 수 없기 때문에 return 0

2. BFS 알고리즘을 사용한다. <- begin에서 target으로 변환되기까지 "최소" 단계를 구하는 것이기 때문이다. (BFS로 풀 때는 처음으로 target이 나오는 단계가 최소단계가 되지만, DFS의 경우에는 단계 개수의 최솟값을 구하는 과정이 더 필요하다.)

   한 개의 알파벳만 다른 단어들은 서로 인접노드이다.

   2-1. 리스트 words를 순회하면서 현재 단어와 한 개의 알파벳만 다른 단어를 찾는다. (함수 difference_cnt의 리턴값이 1인 단어)
   2-2. 현재 단어와 한 개의 알파벳만 다른 단어가 이전에 방문된 적이 없는 노드이면 다음에 방문할 노드들이 있는 대기큐(q)에 넣는다.
   2-3. 현재 단어가 target과 같으면 현재 depth가 최소 단계가 되므로 변수 answer에 넣고 while문 탈출

⌨ 코드

from collections import deque

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

def solution(begin, target, words):
    answer = 0

    if target not in words:
        return 0

    q = deque()
    visited = [begin]
    q.append((begin,0))

    # bfs 시작
    while q:
        cur_word, depth = q.popleft()

        if cur_word == target:
            answer = depth
            break

        for word in words:
            if differences_cnt(cur_word, word) == 1 and word not in visited:
                visited.append(word)
                q.append((word, depth+1))      

    return answer

😊 느낀점

level3이어서 겁을 먹어서 그런지 처음에 어떻게 풀어야할지 감을 못 잡았었다.
그리고 이전에 풀었던 DFS, BFS 문제들은 인접된 노드들이 주어졌는데, 이 문제는 내가 직접 '인접하게 되는 조건'을 찾아야 하는 거라서 생소하기도 했다.
이외에는 기본적인 BFS알고리즘을 응용없이 그대로 쓰는 거라서 어렵지 않게 문제를 풀 수 있었다.