[DAY80] Algorithm : Word Conversion

이번 포스트는 주어진 단어 집합 내에서 "begin" 단어를 "target" 단어로 변환하는 가장 짧은 변환 과정의 단계를 찾는 문제 풀이를 다뤘다. 한 번에 한 글자만 바꾸는 제약 조건이 있었고, 이는 곧 가중치가 없는 그래프에서의 최단 경로를 찾는 문제임을 파악했다. 따라서 효율적인 탐색 알고리즘인 너비 우선 탐색 (BFS)을 사용하여 문제를 해결했다.

---

❓ 문제 분석

• 목표: begin 단어에서 target 단어로 변환하는 최소 변환 횟수를 구해야 한다.
• 제약 조건: 단어의 개수($N$)는 최대 50개, 길이($L$)는 10 이하이다.
• 핵심 키워드: "가장 짧은 변환 과정", "한 번에 한 개의 알파벳만 바꿈" $\rightarrow$ BFS(최단 경로), 그래프

---

💡 풀이 설계

이 문제는 단어들을 노드(Node)로 보고, 한 글자만 다른 단어들 사이에 간선(Edge)이 있다고 보는 그래프 최단 경로 문제이다. 가중치가 없으므로 BFS가 가장 적합하다.

1. 시도했던 접근 (First Attempt)

• 처음에는 재귀 호출을 이용한 DFS로 접근하여 모든 경로를 탐색해 보려 했다.
• 하지만 DFS는 최단 경로를 보장하지 않으며, 모든 경로를 탐색해야 하므로 불필요하게 깊이 탐색을 시도할 수 있다. 최단 거리라는 목표에 맞지 않아 기각했다.

2. 최종 해결책 (Solution)

• 너비 우선 탐색 (BFS)을 사용하여 시작점에서 거리가 1, 2, 3...인 노드들을 순서대로 탐색한다.
• 탐색 전략 선택:
  • 인접 노드를 찾을 때, 모든 단어 목록($N$)을 순회하며 비교하는 방법($O(N \cdot L)$)과, 현재 단어를 'a'~'z'로 변형해보고 목록에 있는지 확인하는 방법($O(26 \cdot L)$)이 있다.
  • $N$이 작을 땐 전자가 빠를 수 있으나, 단어 집합이 커질수록($N$이 증가할수록) 변형 후 조회하는 방식이 훨씬 효율적이므로 후자를 택했다.
• 예상 시간 복잡도: $O(V \cdot L \cdot 26)$ (단어 개수 $V$, 단어 길이 $L$)
• 알고리즘 흐름:
  1. 단어 집합 변환: words 벡터를 $O(1)$ 조회가 가능한 std::unordered_set으로 변환한다.
  2. 초기화: queue에 (begin, 0)을 넣고, visited 집합에 begin을 기록한다.
  3. 탐색 (BFS):
     • 큐에서 단어를 꺼내 target인지 확인한다.
     • 현재 단어의 각 자리를 'a'~'z'로 교체해보며 유효한 단어(집합에 존재 && 미방문)를 찾아 큐에 넣는다.

---

💻 코드 구현

#include <string>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

// BFS 탐색 상태를 위한 구조체
struct State {
    string word;
    int steps; // 시작 단어로부터의 변환 횟수 (거리)
};

int solution(string begin, string target, vector<string> words) {
    // 빠른 탐색(O(1))을 위해 unordered_set으로 변환
    unordered_set<string> word_set(words.begin(), words.end());
    
    // 예외 처리: target이 목록에 없으면 변환 불가
    if (word_set.find(target) == word_set.end()) {
        return 0;
    }
    
    // BFS 준비
    queue<State> q;
    unordered_set<string> visited; 

    q.push({ begin, 0 });
    visited.insert(begin);
    
    // BFS 탐색
    while (!q.empty()) {
        State current = q.front();
        q.pop();

        string current_word = current.word;
        int current_steps = current.steps;

        if (current_word == target) {
            return current_steps;
        }

        // 인접 단어 탐색: 한 글자만 다른 단어 찾기
        for (size_t i = 0; i < current_word.size(); ++i) {
            char original_char = current_word[i]; // 복원용 저장
            
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c == original_char) continue; // 같은 글자는 패스

                current_word[i] = c; // 글자 변형
                
                // 유효성 검사: 목록에 있고, 방문하지 않았으면
                if (word_set.count(current_word) && !visited.count(current_word)) {
                    visited.insert(current_word);
                    q.push({ current_word, current_steps + 1 });
                }
            }
            // 다음 인덱스 탐색을 위해 원래 글자로 복원 (Backtracking)
            current_word[i] = original_char; 
        }
    }
    
    return 0;
}

---

🐛 시행착오 및 디버깅

• 문제점: 처음에는 단어를 변형할 때, 원본을 복사하지 않고 수정한 뒤 복원하지 않고 다음 루프를 진행하는 실수를 했다. 이로 인해 hit -> hot이 되어야 하는데, ait -> bot 처럼 엉뚱한 단어에서 변형이 시작되었다.
• 해결: 내부 루프가 끝난 뒤 current_word[i] = original_char; 코드를 추가하여, 항상 원본 단어 상태에서 한 글자만 바뀐 경우를 탐색하도록 수정했다. 이를 통해 불필요한 문자열 복사 비용도 줄일 수 있었다.

---

✅ 오늘의 회고

항목	내용
유형	BFS / Graph (최단 경로)
체감 난이도	중
복잡도	시간: $O(V \cdot L \cdot 26)$, 공간: $O(V)$
새로 배운 것	1. 가중치 없는 최단 경로는 BFS가 정석이다. 2. 인접 노드를 찾는 방식이 $N$ 순회와 $26 \times L$ 변형 두 가지가 있음을 비교해 보았다. 3. 문자열 변형 시 상태 복원(Backtracking logic)의 중요성을 체감했다.