[프로그래머스][C++] 단어 변환

단어 변환

문제 링크

단어 변환

분석

begin을 target으로 변환해야합니다.

변환할 때 규칙은 다음과 같습니다.

• 가장 짧은 변환 과정을 찾아야합니다.
• 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
• words에 있는 단어로만 변환할 수 있습니다.
  • words에는 중복되는 단어가 없습니다.

모든 단어는 알파벳 소문자로만 이루어져 있습니다.
모든 단어의 길이는 같습니다.

변환할 수 없는 경우 0을 반환합니다.

풀이

#include <string>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

// 두 단어가 한 글자만 다른 경우 true를 반환한다.
bool isNearWord(const string& curWord, const string& targetWord)
{
    int diffCount = 0;
    
    // 각 단어를 순회하면서 비교한다.
    for (int i = 0; i < curWord.size(); ++i)
    {
        if (curWord[i] != targetWord[i])
        {
            ++diffCount;
            
            // 두 글자 이상 다른 경우 변환 불가능하므로, false를 반환한다.
            if (diffCount > 1)
            {
                return false;
            }
        }
    }
    
    return diffCount == 1;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    // 단어의 방문 여부를 저장하는 해시맵
    unordered_map<string, bool> visited;
    
    // BFS를 위한 큐로 현재 단어와 변환 횟수를 저장한다.
    queue<pair<string, int>> q;
    q.push({begin, 0});
    
    // 시작 단어를 방문 처리한다.
    visited[begin] = true;
    
    while (!q.empty())
    {
        // 현재 단어와 지금까지의 변환 횟수를 꺼낸다.
        auto [current, count] = q.front();
        q.pop();
        
        // 현재 단어와 타겟 단어가 같은 경우 변환 횟수를 반환한다.
        if (current == target)
        {
            return count;
        }
        
        // 변환할 수 있는 단어를 순회합니다.
        for (const auto& word : words)
        {
            // 방문하지 않고, 변환할 수 있는 경우
            if (!visited[word] && isNearWord(current, word))
            {
                visited[word] = true;
                q.push({word, count + 1});
            }
        }
    }
    
    // 타겟 단어를 만들 수 없다.
    return 0;
}

성능 요약

시간 복잡도는 $O(n^2) \times O(l)$입니다.

• isNearWord 함수 $O(l)$
  • l은 단어의 길이
• BFS 탐색 $O(n^2)$
  • n은 words에 포함된 단어의 개수
• $O(n^2) \times O(l)$

공간 복잡도는 $O(n)$입니다.

• 단어의 방문 여부를 저장하는 해시맵 unordered_map<string, bool> visited $O(n)$
• BFS를 위한 큐 $O(n)$
• $O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.02ms, 3.6MB)
테스트 3 〉 통과 (0.03ms, 4.21MB)
테스트 4 〉 통과 (0.02ms, 4.03MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)