[Programmers/C++] 단어 변환

시간 복잡도

• 단어 배열 words에는 최대 50개의 단어가 존재합니다.
• DFS를 이용해 모든 경우의 수를 구하면 최대 $O(N!)$ 이므로 최대 $50!$이라 시간 초과가 발생할 수 있습니다.
• BFS를 이용하면 $O(N)$의 시간 복잡도로 문제를 해결할 수 있습니다.

문제 접근법

• 시작 단어에서 알파벳의 개수가 1개만 다른 단어를 탐색하며 깊이를 카운트 합니다.
• 현재 단어와 타겟 단어가 같다면 현재 깊이를 반환하고 찾지 못했으면 0을 반환합니다.

코드

BFS 풀이

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

using namespace std;

bool canChange(const string &a, const string &b) {
    int diff = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) diff++;
        if (diff > 1) return false;
    }
    return diff == 1;
}

int solution(string begin, string target, vector<string> words) {
    queue<pair<string, int>> q;
    vector<bool> visited(words.size(), false);

    q.push({begin, 0});

    while (!q.empty()) {
        auto [current, depth] = q.front();
        q.pop();

        if (current == target) return depth;

        for (int i = 0; i < words.size(); i++) {
            if (!visited[i] && canChange(current, words[i])) {
                visited[i] = true;
                q.push({words[i], depth + 1});
            }
        }
    }

    return 0;
}

DFS 풀이

#include <string>
#include <vector>
#include <cmath>
#include <climits>

using namespace std;


static bool visited[51] = {};
static bool flag=false;
static int answer=INT_MAX;

void DFS(vector<string>& words, string begin, string target, int depth)
{
    if(begin == target)
    {
        flag = true;
        answer = min(answer, depth);
        return;
    }
        
    
    for(int i=0; i<words.size(); i++)
    {
        if(!visited[i])
        {
            int count=0;
            for(int j=0; j<words[i].length(); j++)
            {
                if(words[i][j]!=begin[j])
                    count++;
            }
            
            if(count==1)
            {
                visited[i]=true;
                DFS(words, words[i], target, depth+1);
                visited[i]=false;
            }
        }
    }

    
}

int solution(string begin, string target, vector<string> words) {
    
    DFS(words, begin, target, 0);
    
    if(!flag)
        answer=0;
    
    return answer;
}