C++ Word Ladder 문제 완벽 정리: BFS로 최단 단어 변환 체인 길이 구하기

문제 소개

이 문제에서는 하나의 사전(Dictionary)과 두 단어, 즉 'start'(시작 단어)와 'target'(목표 단어)이 주어집니다. 우리의 과제는 시작 단어에서 출발해 목표 단어에 도달하는 체인(사다리)을 만드는 것입니다. 이때 체인에 포함된 각 단어는 바로 앞 단어와 정확히 한 글자만 달라야 하며, 해당 단어는 반드시 사전에 존재해야 합니다. 목표 단어는 항상 사전에 포함되어 있고, 모든 단어의 길이는 서로 같다는 조건이 주어집니다.

프로그램의 최종 목표는 시작 단어에서 목표 단어까지 이르는 최단 경로의 길이를 반환하는 것입니다.

예시를 통해 문제를 더 자세히 살펴보겠습니다.

입력 예시

Dictionary = {'HEAL', 'HATE', 'HEAT', 'TEAT', 'THAT', 'WHAT', 'HAIL', 'THAE'}
Start = 'HELL'
Target = 'THAE'

출력 예시

해설

HELL → HEAL → HEAT → TEAT → THAT → THAE

위 경로를 보면 각 단계마다 단 한 글자씩만 변경되면서 목표 단어 'THAE'에 도달하며, 체인을 이루는 단어는 총 6개입니다.

접근 방법: 너비 우선 탐색(BFS)

이 문제는 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 각 단어를 그래프의 노드로, 한 글자만 차이 나는 단어들을 서로 연결하는 간선으로 생각하면, 최단 체인을 찾는 문제는 곧 그래프에서의 최단 경로 탐색 문제와 같아집니다. BFS는 이러한 최단 경로를 보장하는 대표적인 탐색 기법입니다.

구체적인 동작 과정은 다음과 같습니다.

시작 단어를 큐(queue)에 삽입하고, 레벨(level) 값을 초기화합니다.
큐에서 단어를 하나 꺼낸 뒤, 각 자리의 문자를 'a'부터 'z'까지 하나씩 교체해 봅니다.
교체된 단어가 목표 단어와 일치하면 현재 레벨 + 1을 반환합니다.
교체된 단어가 사전에 존재하면 큐에 추가하고, 같은 단어를 중복 방문하지 않도록 사전에서 제거합니다.
큐가 빌 때까지 위 과정을 반복하며, 끝까지 목표 단어에 도달하지 못하면 0을 반환합니다.

C++ 구현 코드

앞서 설명한 해결 방법을 C++로 구현한 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
int wordLadder(string start, string target, set<string>& dictionary) {
   if (dictionary.find(target) == dictionary.end())
      return 0;
   int level = 0, wordlength = start.size();
   queue<string> ladder;
   ladder.push(start);
   while (!ladder.empty()) {
      ++level;
      int sizeOfLadder = ladder.size();
      for (int i = 0; i < sizeOfLadder; ++i) {
         string word = ladder.front();
         ladder.pop();
         for (int pos = 0; pos < wordlength; ++pos) {
            char orig_char = word[pos];
            for (char c = 'a'; c <= 'z'; ++c) {
               word[pos] = c;
               if (word == target)
                  return level + 1;
               if (dictionary.find(word) == dictionary.end())
                  continue;
               dictionary.erase(word);
               ladder.push(word);
            }
            word[pos] = orig_char;
         }
      }
   }
   return 0;
}
int main() {
   set<string> dictionary;
   dictionary.insert("heal");
   dictionary.insert("heat");
   dictionary.insert("teat");
   dictionary.insert("that");
   dictionary.insert("what");
   dictionary.insert("thae");
   dictionary.insert("hlle");
   string start = "hell";
   string target = "thae";
   cout<<"Length of shortest chain from '"<<start<<"' to '"<<target<<"' is: "<<wordLadder(start, target, dictionary);
   return 0;
}

실행 결과

Length of shortest chain from 'hell' to 'thae' is: 6

실행 결과를 보면, 시작 단어 'hell'에서 목표 단어 'thae'까지의 최단 체인 길이가 6으로 올바르게 계산된 것을 확인할 수 있습니다.

마무리 및 복잡도 분석

Word Ladder 문제는 BFS의 전형적인 활용 사례입니다. 이 알고리즘의 시간 복잡도는 O(N × L × 26)입니다. 여기서 N은 사전에 포함된 단어의 개수, L은 단어의 길이를 의미하며, 각 단어의 모든 자리를 알파벳 26글자로 교체해 가며 확인하기 때문입니다. 공간 복잡도 역시 사전과 큐에 저장되는 데이터에 비례하여 O(N × L)입니다. 이처럼 상태를 한 단계씩 확장해 가며 최단 거리를 찾는 BFS 접근법은 다양한 그래프 탐색 문제에서 널리 활용되므로, 개념과 구현 방법을 함께 익혀두는 것이 좋습니다.