🧩 문제 접근 방식

두 단어가 서로 한 글자만 다른 경우에만 변환이 가능하다는 조건이 주어져 있기 때문에 단어 간 연결 관계를 그래프로 보고, 시작 단어에서 목표 단어까지의 경로를 탐색하는 문제로 해석할 수 있습니다.

이러한 경로 탐색 문제를 해결하기 위해 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색) 방식으로 접근했습니다.

🔍 DFS (깊이 우선 탐색)

DFS는 한 방향으로 계속 깊게 탐색하다가 더 이상 갈 곳이 없으면 되돌아가서 다른 경로를 탐색하는 방식입니다.

보통 재귀 함수를 통해 구현되며, 모든 경우의 수를 확인할 때 유용하게 사용이 됩니다.

def solution(begin, target, words):
    # min_steps는 최소 단계 수를 추적할 리스트, 초기값은 무한대로 설정
    min_steps = [float('inf')]
    # words 리스트에서 각 단어가 사용됐는지 여부를 저장(중복방지를 위함)
    visited = [False] * len(words)
    
    # 두 단어를 비교해서 한 글자만 다른지 확인하는 함수
    def one_letter_diff(a, b):
        diff = 0
        for i in range(len(a)):
            if a[i] != b[i]:
                diff += 1
        if diff == 1:
            return True
        return False
    
    # 재귀함수 정의, current_word(현재 단어), steps(지금까지 변환한 횟수)
    def dfs(current_word, steps):
        if current_word == target:
            min_steps[0] = min(min_steps[0], steps)
            return
        
        for i in range(len(words)):
            if not visited[i] and one_letter_diff(current_word, words[i]):
                visited[i] = True
                dfs(words[i], steps + 1)
                visited[i] = False
    
    # 시작 단어에서부터 DFS 탐색 시작, 단계 수는 0
    dfs(begin,0)
    
    # min_steps가 여전히 무한대면 0을 그게 아니면 min_steps[0]을 반환한다.
    return 0 if min_steps[0] == float('inf') else min_steps[0]
    
    
    return answer

🔍 BFS (너비 우선 탐색)

BFS는 가까운 노드부터 차례대로 탐색합니다. 즉, 모든 단어를 한 단계씩 변환해 가며 확인하기 때문에 최단 경로를 찾는 데 유용하게 사용이 됩니다.


# deque는 양방향 큐 이고, 일반 리스트보다 pop, append가 더 빠르기 때문에 BFS구현에 자주 사용된다.
from collections import deque

def solution(begin, target, words):
    # target 단어가 words안에 없으면 바로 0 반환
    if target not in words:
        return 0
    
    # BFS탐색을 위한 큐에 시작단어와 변환 횟수를 튜플 형태로 넣는다.
    queue = deque([(begin, 0)])
    visited = [False] * len(words)
    
    def one_letter_diff(a,b):
        diff = 0
        for i in range(len(a)):
            if a[i] != b[i]:
                diff += 1
        if diff == 1:
            return True
        return False
    
    # 큐에 요소가 있을 동안 계속 반복
    while queue:
        # 큐에서 현재 단어와 변환 횟수를 꺼낸다.
        # popleft()는 큐의 맨 앞에서 꺼내는 함수
        current_word, steps = queue.popleft()
        if current_word == target:
            return steps
        for i in range(len(words)):
            if not visited[i] and one_letter_diff(current_word, words[i]):
                visited[i] = True
                queue.append((words[i], steps + 1))
    return 0

✅ queue = deque([(begin, 0)]) 에서 튜플(begin, 0)로 넣는 이유?

내부 값이 변경되지 않으므로 변경이 불가능한 튜플이 더 안전하고 효율적입니다.
리스트를 써도 문제는 없지만, 튜플을 사용하여 불변성(immutable)을 유지하는 것이 코드 안정성에 좋습니다.

✅ 왜 deque를 사용하는가?

리스트에서 pop(0)을 사용하면 앞의 모든 요소가 한 칸씩 이동해야 되기 때문에, O(n)의 시간복잡도를 가지고, 이 행위가 반복되면 성능 저하가 발생합니다.
반면에 deque는 양쪽 끝에서 삽입/삭제가 가능하기 때문에, O(1)의 시간복잡도를 가져 성능 저하 없이 빠르게 처리가 가능합니다. (popleft() → 맨 앞에서 바로 제거, append() → 맨 뒤에 바로 추가)

✨ 마무리 정리

구분	DFS	BFS
탐색 방식	깊이 우선	너비 우선
구현 방식	재귀 함수 사용	큐 사용
사용 목적	모든 경우의 수 확인	최단 경로 탐색
사용 예	미로 탐색, 퍼즐 해결	네트워크 연결, 최단 경로 거리

DFS는 깊이 있게 모든 경로를 탐색할 수 있다는 장점이 있고, BFS는 단계별로 가장 빠르게 도달하는 최단 경로를 찾는 데 효율적임을 알 수 있었습니다.

📌 아직 배우는 중이라 부족한 부분이 있을 수 있습니다.
혹시 잘못된 내용이나 더 나은 방법이 있다면 알려주세요 🙏
감사합니다! 😄