단어 변환

1. 핵심 아이디어: 최단 경로 찾기

이 문제는 begin에서 시작해 target에 도달하는 최소 단계를 찾는 문제입니다.

• **BFS(너비 우선 탐색)**를 사용하는 것이 가장 유리합니다. BFS는 시작점에서 가까운 노드부터 탐색하므로, target을 발견하는 순간이 곧 최단 경로가 됩니다.
• **DFS(깊이 우선 탐색)**로도 풀 수 있지만, 모든 경로를 확인하며 최솟값을 업데이트해야 하므로 BFS보다 비효율적일 수 있습니다.

2. 그래프 정의 (연결성 확인)

두 단어가 연결되어 있다는 것은 **"알파벳이 딱 하나만 다르다"**는 뜻입니다. 이를 판별하는 함수를 먼저 작성하세요.

• 비교 로직: 두 단어의 길이는 같으므로, 인덱스별로 비교하여 다른 문자의 개수가 정확히 1일 때만 True를 반환합니다.

3. BFS 구현 프로세스

BFS를 사용할 때 (현재 단어, 단계 수)를 큐(deque)에 담아 관리하면 관리가 편합니다.

1. 예외 처리: 만약 target이 words 배열에 없다면 절대 도달할 수 없으므로 즉시 0을 반환합니다.
2. 큐(Queue) 초기화: deque([(begin, 0)]) 형태로 시작합니다.
3. 방문 처리(Visited): 이미 변환했던 단어를 다시 변환하면 무한 루프에 빠질 수 있습니다. set이나 리스트를 활용해 방문한 단어를 기록하세요.
4. 탐색:
   • 큐에서 단어를 꺼냅니다.
   • 현재 단어가 target과 같다면 현재까지의 단계 수를 반환합니다.
   • words 리스트를 돌며 아직 방문하지 않았고, 현재 단어와 한 글자만 다른 단어들을 찾아 큐에 넣고 방문 표시를 합니다.

---

4. 파이썬 풀이 팁

파이썬의 zip 함수를 활용하면 두 단어의 차이를 매우 쉽게 계산할 수 있습니다.

Python

 

# 한 글자만 다른지 확인하는 파이썬다운 방법
diff_count = sum(1 for a, b in zip(word1, word2) if a != b)
if diff_count == 1:
    # 연결 가능!

이 문장은 파이썬의 '컴프리헨션(Comprehension)'과 '제너레이터(Generator)' 문법을 활용한 아주 간결하고 효율적인 코드입니다.

이 한 줄을 구성하는 4가지 요소를 단계별로 쪼개서 설명해 드릴게요.

---

1. zip(current_word, word) : 두 단어를 나란히 묶기

zip 함수는 두 개의 리스트(또는 문자열)를 인덱스별로 짝을 지어줍니다.

• 예: current_word = "hit", word = "hot" 일 때
• zip 결과: ('h', 'h'), ('i', 'o'), ('t', 't')

2. for a, b in ... : 짝지은 글자 꺼내기

위에서 만든 짝들을 하나씩 꺼내서 앞의 글자는 a에, 뒤의 글자는 b에 담습니다.

3. if a != b : 서로 다른 글자만 골라내기

a와 b를 비교해서 값이 다를 때만 다음 동작을 수행하라는 필터링 조건입니다.

4. sum(1 for ...) : 개수 세기

조건(a != b)이 참일 때마다 1을 생성(yield)하고, sum 함수가 이 1들을 모두 더합니다. 결과적으로 글자가 다른 위치의 총 개수가 나옵니다.

---

실제 동작 예시 ( "hit" vs "hot" )

1. zip 단계: ('h', 'h'), ('i', 'o'), ('t', 't') 세 쌍이 생성됨.
2. 비교 단계:
   • 'h' == 'h': 같으므로 넘어감.
   • 'i' != 'o': 다르므로 1 생성!
   • 't' == 't': 같으므로 넘어감.
3. 합계 단계: 최종적으로 생성된 1이 하나뿐이므로 sum 결과는 1.

---

왜 이렇게 쓰나요? (장점)

만약 이 한 줄을 일반적인 for문으로 푼다면 아래와 같이 4줄이나 필요합니다.

Python

 

diff_count = 0
for i in range(len(current_word)):
    if current_word[i] != word[i]:
        diff_count += 1

**파이썬다운 방식(Pythonic Way)**인 sum(1 for a, b in zip(...))을 사용하면:

1. 가독성: "두 단어를 묶어서 글자가 다르면 1씩 더해라"라는 로직이 한눈에 보입니다.
2. 속도: 내부적으로 최적화된 반복문을 사용하므로 성능 면에서도 유리합니다.
3. 유연성: 단어의 길이를 따로 계산(len())할 필요 없이 zip이 알아서 처리해 줍니다.

 

5. 요약하자면

• 상태(Node): 각 단어
• 간선(Edge): 한 글자만 차이 나는 단어 사이의 관계
• 목표: begin에서 target 노드까지 가는 최소 간선 개수 구하기

---

 

프로그래머스 '단어 변환' 문제를 파이썬의 BFS(너비 우선 탐색)를 활용해 해결하는 완성된 코드와 상세 설명을 준비했습니다.

최단 거리를 구하는 문제이므로 collections.deque를 활용한 BFS가 가장 정석적인 접근입니다.

1. 문제 해결 코드 (Python)

Python

 

from collections import deque  # 효율적인 큐(Queue) 구현을 위해 deque 라이브러리를 가져옵니다.

def solution(begin, target, words):
    # 1. 예외 처리: 목표 단어(target)가 단어 뭉치(words)에 없으면 도달 불가능하므로 0을 반환합니다.
    if target not in words:
        return 0
    
    # 2. BFS 탐색 준비
    # queue에는 (현재 단어, 현재까지 변환된 단계 수)를 튜플 형태로 저장합니다.
    # 시작 단어(begin)부터 탐색을 시작하며, 처음 단계는 0입니다.
    queue = deque([(begin, 0)])
    
    # 방문한 단어를 기록할 집합(set)입니다. 이미 확인한 단어를 다시 확인하는 무한 루프를 방지합니다.
    visited = set()
    
    # 3. 큐가 빌 때까지 반복 탐색 (BFS)
    while queue:
        # 가장 먼저 들어온 데이터를 꺼냅니다(FIFO). BFS이므로 먼저 들어온 것이 가장 짧은 경로입니다.
        current_word, depth = queue.popleft()
        
        # [탈출 조건] 현재 단어가 목표 단어(target)와 일치하면 현재까지의 단계를 즉시 반환합니다.
        if current_word == target:
            return depth
        
        # 단어 뭉치(words) 전체를 순회하며 다음에 변환할 후보를 찾습니다.
        for word in words:
            # 아직 방문하지 않은 단어 중에서만 찾습니다.
            if word not in visited:
                # 현재 단어와 후보 단어의 글자 차이를 계산합니다.
                # zip을 통해 한 글자씩 비교하여 서로 다른 경우만 1씩 더합니다.
                diff_count = sum(1 for a, b in zip(current_word, word) if a != b)
                
                # 차이가 딱 1글자라면 다음 단계로 변환이 가능합니다.
                if diff_count == 1:
                    visited.add(word)           # 이 단어를 방문 처리합니다.
                    queue.append((word, depth + 1)) # 큐에 추가하며 단계를 1 증가시킵니다.
                    
    # 모든 경로를 탐색했음에도 target을 만나지 못한 경우 0을 반환합니다.
    return 0

---

2. 코드 상세 설명

핵심 로직 1: zip을 이용한 단어 비교

sum(1 for a, b in zip(current_word, word) if a != b)는 두 단어를 나란히 놓고 인덱스별로 비교하여 다른 글자의 개수를 세는 파이썬다운 방식입니다. 이 값이 1일 때만 다음 단계로 이동할 수 있습니다.

핵심 로직 2: BFS의 특징 활용

BFS는 레벨 단위로 탐색을 진행합니다.

• 1단계: begin에서 한 글자 바꿔서 갈 수 있는 모든 단어 탐색
• 2단계: 1단계 단어들에서 다시 한 글자 바꿔서 갈 수 있는 모든 단어 탐색
• 따라서 처음으로 target과 일치하는 단어가 큐에서 나오는 순간, 그 경로가 반드시 최소 단계임이 보장됩니다.

핵심 로직 3: visited 집합(Set)

visited에 이미 확인한 단어를 넣어두지 않으면, 'hot' -> 'dot' -> 'hot' 처럼 단어가 무한히 반복되어 돌아가는 현상이 발생합니다. set은 탐색 속도가 $O(1)$이므로 효율적입니다.

---

3. 복잡도 분석

• 시간 복잡도: $O(N \times L \times N)$
  • $N$은 단어의 개수 (최대 50), $L$은 단어의 길이 (최대 10)입니다.
  • 큐에서 단어를 하나씩 꺼낼 때마다(N) 전체 단어 리스트를 순회하며(N) 각 단어의 글자를 비교(L)하기 때문입니다.
  • 이 문제의 제한 사항에서는 매우 넉넉하게 통과되는 수준입니다.