프로그래머스: [단어 변환]

📌 프로그래머스: [단어 변환]

🔗 문제 링크

---

문제 접근 방식 💡

• begin에서 target으로 단어를 변환하는 과정에서 한 번에 하나의 문자만 변경 가능.
• 주어진 words 리스트 내에서 변환을 수행하며, 최소 단계로 target에 도달하는 경로를 찾아야 함.
• BFS(너비 우선 탐색)을 사용하여 가장 빠른 변환 경로를 탐색.

---

Solution 💻

from collections import deque
    
def solution(begin, target, words):
    if target not in words:
        return 0
    
    visited = set()
    q = deque()
    q.append((begin, 0))
    visited.add(begin)
    
    while q:
        p, result = q.popleft()
        if p == target:
            return result
        for word in words:
            if word not in visited:
                diff = sum(1 for a, b in zip(p, word) if a != b)
                if diff == 1:
                    visited.add(word)
                    q.append((word, result + 1))
                    
    return 0

시간 복잡도 분석 ⏲️

• BFS 탐색: O(N * M),
  • N은 단어 개수, M은 단어 길이.
  • 각 단어에 대해 문자 비교 연산 수행 (O(M)).
  • 최악의 경우 O(50 * 10) = O(500) 정도로 충분히 수행 가능.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(N),
  • visited 집합과 큐에 저장된 단어 개수에 비례.