[Programmers] 단어 변환

🔦 문제 링크

✍️ 풀이

---

간단한 BFS문제

• 현재 word와 1개 차이가 나는 다음 단어를 선택해서 큐에 넣어주면 된다.
  BFS를 통해 가능한 모든 하나 차이나는 단어를 검사하고 target을 찾으면 현재 단계 반환.
  BFS 끝까지 target을 찾지 못하면 0을 반환하도록 한다.

🛠 코드

---

from collections import deque

def solution(begin, target, words):
    answer = 0
    check = dict()
    for word in words:
        check[word] = False
    if target not in words:
        return 0
    mn = len(words) + 1
    q = deque()
    q.append((begin, 0))
    while q:
        curr, curr_count = q.popleft()
        if curr == target:
            return curr_count
        for word in words:
            count = 0
            for i in range(len(word)):
                if curr[i] == word[i]:
                    continue
                else:
                    count += 1
                    if count > 1:
                        break
            if count == 1:
                if check[word] is False:
                    check[word] = True
                    q.append((word, curr_count + 1))
    return 0

📝 정리

---

🎈 참조

---