Level 3. 단어 변환

Level 3. 단어 변환

 

 

전형적인 BFS 문제다.

• 최솟값을 구해야하므로 DFS가 아닌 BFS를 사용해야 한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <unordered_map>

using namespace std;

bool canConvert(string& a, string& b)
{
    static const int DIFF = 1;
    int diff = 0;

    for (int i = 0; i < a.length(); ++i)
        diff += (a[i] != b[i]);

    return (diff == DIFF);
}

int solution(string begin, string target, vector<string> words)
{
    int answer = 0;
    queue<pair<int, string>> que;
    unordered_map<string, unordered_map<string, bool>> isUsed;

    que.push({0, begin});

    while (!que.empty())
    {
        int level = que.front().first;
        string s = que.front().second;
        que.pop();

        if (s == target)
            return level;

        for (string& word : words)
        {
            if (!isUsed[s][word] && canConvert(s, word))
            {
                isUsed[s][word] = true;
                que.push({level + 1, word});
            }
        }
    }
    
    return 0;
}

 

방문 검사를 unordered_map이 아닌 1차원 vector로도 해결할 수 있었다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

bool canConvert(string& a, string& b)
{
    static const int DIFF = 1;
    int diff = 0;

    for (int i = 0; i < a.length(); ++i)
        diff += (a[i] != b[i]);

    return (diff == DIFF);
}

int solution(string begin, string target, vector<string> words)
{
    int answer = 0;
    queue<pair<int, string>> que;
    vector<bool> isUsed(words.size(), false);

    que.push({0, begin});

    while (!que.empty())
    {
        int level = que.front().first;
        string s = que.front().second;
        que.pop();

        if (s == target)
            return level;

        for (int i = 0; i < words.size(); ++i)
        {
            if (!isUsed[i] && canConvert(s, words[i]))
            {
                isUsed[i] = true;
                que.push({level + 1, words[i]});
            }
        }
    }
    
    return 0;
}