Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 워드 래더(Word Ladder): BFS로 최단 변환 시퀀스 구하기

문제 설명

두 단어(beginWord와 endWord)와 사전 역할을 하는 단어 목록이 주어졌을 때, beginWord에서 endWord까지 도달하는 최단 변환 시퀀스의 길이를 구하는 문제입니다. 변환 과정은 다음 규칙을 따릅니다.

  • 한 번에 한 글자씩만 변경할 수 있습니다.
  • 변환된 각 단어는 반드시 단어 목록에 존재해야 하며, beginWord는 변환된 단어에 포함되지 않습니다.

문제를 풀기 전에 다음 조건들도 함께 기억해 두어야 합니다.

  • 가능한 변환 시퀀스가 존재하지 않으면 0을 반환합니다.
  • 모든 단어는 길이가 서로 같습니다.
  • 모든 단어는 소문자 영문자로만 이루어져 있습니다.
  • 단어 목록에는 중복이 없다고 가정할 수 있습니다.

예를 들어 입력이 beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]라고 한다면 출력은 5입니다. 가장 짧은 변환 경로가 hit → hot → dot → dog → cog이기 때문입니다.

풀이 접근 방법

이 문제는 단어를 노드로, 한 글자 차이 나는 관계를 간선으로 보면 암묵적 그래프의 최단 경로 탐색과 같습니다. 따라서 BFS(너비 우선 탐색)를 적용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 단어의 특정 자리를 '*'로 치환한 와일드카드 패턴(예: "h*t")을 키로 삼아, 같은 패턴을 공유하는 단어들을 미리 묶어 두는 것입니다. 이렇게 하면 한 글자만 다른 인접 단어를 매번 전체 목록과 비교하지 않고도 즉시 찾을 수 있습니다.

구체적인 절차는 다음과 같습니다.

  1. 패턴 생성 함수 정의: 위치 j와 문자열 s를 받아, j번째 글자를 '*'로 바꾼 문자열을 반환하는 putStar 메서드를 만듭니다.
  2. 예외 처리: endWord가 단어 목록에 없거나, beginWord·endWord·목록 중 하나라도 비어 있으면 0을 반환합니다.
  3. 패턴 버킷 생성: 문자열 키와 벡터 값을 갖는 맵 m을 준비하고, 목록의 모든 단어 x에 대해 각 자리 j마다 putStar(j, x)로 패턴을 만든 뒤 m[패턴]에 x를 추가합니다.
  4. BFS 초기화: 큐 q를 만들고 (beginWord, 1) 쌍을 넣으며, 방문 여부를 기록할 맵 visited를 준비합니다.
  5. BFS 반복: 큐가 빌 때까지 다음을 수행합니다.
    • 큐에서 (단어 x, 현재 길이 l)을 꺼냅니다.
    • x의 각 자리 i에 대해 패턴 temp = putStar(i, x)를 계산하고, m[temp]에 속한 모든 단어 aa를 검사합니다.
    • aa가 endWord와 같으면 즉시 l + 1을 반환합니다.
    • aa를 아직 방문하지 않았다면 (aa, l + 1)을 큐에 넣고 visited[aa]를 1로 설정합니다.
  6. 실패 처리: 큐를 모두 소진했는데도 endWord에 도달하지 못하면 0을 반환합니다.

C++ 구현 코드

아래 예제를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string putStar(int j, string s){
        string temp = "";
        for(int i = 0; i < s.size(); i++){
            if(i == j)temp += "*";
            else temp += s[i];
        }
        return temp;
    }
    int ladderLength(string b, string e, vector<string>& w) {
        if(find(w.begin(), w.end(), e) == w.end() || !b.size() || !e.size() || !w.size())return 0;
        map < string , vector <string> > m;
        for(int i = 0; i < w.size(); i++){
            string x = w[i];
            for(int j = 0; j < x.size(); j++){
                string inter = putStar(j,x);
                m[inter].push_back(x);
            }
        }
        queue < pair <string, int> > q;
        q.push({b, 1});
        map <string, int> visited;
        while(!q.empty()){
            pair < string, int > s = q.front();
            q.pop();
            string x = s.first;
            int l = s.second;
            for(int i = 0; i < x.size(); i++){
                string temp = putStar(i ,x);
                for(int j = 0; j < m[temp].size(); j++){
                    string aa = m[temp][j];
                    if(aa == e)return l+1;
                    if(!visited[aa]){
                        q.push({aa, l+1});
                        visited[aa] = 1;
                    }
                }
            }
        }
        int level = 0;
        return 0;
    }
};
main(){
    vector<string> v = {"hot","dot","dog","lot","log","cog"};
    Solution ob;
    cout << (ob.ladderLength("hit", "cog", v));
}

입력

"hit"
"cog"
["hot","dot","dog","lot","log","cog"]

출력

5

복잡도 분석

단어의 개수를 N, 단어의 길이를 L이라고 하면, 패턴 버킷을 만드는 데 O(N × L²)의 시간과 공간이 필요합니다. BFS 탐색 역시 각 단어마다 L개의 패턴을 생성하므로 전체 시간 복잡도는 O(N × L²)입니다. 매 단계마다 모든 단어를 일일이 비교하는 완전 탐색 방식(O(N² × L))보다 훨씬 효율적이라는 점이 이 풀이의 가장 큰 장점입니다.