프로그래머스 | [연습문제] 단어변환

출처

🌐 코딩테스트 연습 - 단어 변환 | 프로그래머스 스쿨

문제

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다. 

입출력 예시

begin target words return

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

풀이

1차 풀이(실패)

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

using namespace std;

vector<int> roots;

bool isConvertable(const string& begin, const string& target)
{
    int count = 0;
    for (int i = 0; i < begin.size(); i++)
    {
        if (begin[i] != target[i])
        {
            count++;
            if (count > 1) return false;
        }
    }

    if (count == 1) 
        return true;
    else 
        return false;
}
void DFS(stack<string>& s, const string& target, const vector<string>& words, 
         vector<vector<int>>& convertMap, vector<bool>& checks, 
         const unordered_map<string, int>& wordIndexes) 
{
    if (s.top() == target) {
        roots.push_back(s.size() - 1); // Depth of transformation
        return;
    }

    for (const auto& index : convertMap[wordIndexes.at(s.top())]) {
        if (checks[index]) {
            s.push(words[index]);
            checks[index] = false;
            DFS(s, target, words, convertMap, checks, wordIndexes);
            s.pop();
            checks[index] = true; // Reset after backtracking
        }
    }
}

int solution(string begin, string target, vector<string> words) 
{
    roots.clear();
    if (find(words.begin(), words.end(), target) == words.end()) 
        return 0; // Target not in words, early return.

    words.push_back(begin);
    vector<vector<int>> convertMap(words.size());
    unordered_map<string, int> wordIndexes;

    for (int i = 0; i < words.size(); i++) {
        wordIndexes[words[i]] = i;
        for (int j = i + 1; j < words.size(); j++) {
            if (isConvertable(words[i], words[j])) {
                convertMap[i].push_back(j);
                convertMap[j].push_back(i);
            }
        }
    }

    stack<string> s;
    s.push(begin);
    vector<bool> checks(words.size(), true);
    checks[checks.size() - 1] = false;

    DFS(s, target, words, convertMap, checks, wordIndexes);

    if (roots.empty()) return 0; // No valid paths found.
    return *min(roots.begin(), roots.end());
}

2차 풀이(DFS, 성공)

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

using namespace std;

vector<int> root;

bool isConvertable(const string& begin, const string& target)
{
    int count = 0;

    for (int i = 0; i < begin.size(); i++)
    {
        if (begin[i] != target[i])
        {
            count++;
        }
    }

    return count == 1;
}

void DFS(const string& current, const string& target, unordered_map<string,bool>& visited, int& count)
{
    if (target == current)
        root.push_back(count);

    for (const auto& word : visited)
    {
        if (isConvertable(current, word.first) && !word.second )
        {
            visited[word.first] = true;
            count++;
            DFS(word.first, target, visited, count);
            count--;
            visited[word.first] = false;
        }
    }

}

int solution(string begin, string target, vector<string> words)
{
    int count = 0;

    queue<string> wordsQ;

    unordered_map<string, bool> visited;
    for (const string& word : words)
    {
        visited[word] = false;
    }

    DFS(begin, target, visited, count);

    return (root.empty()) ? 0 : *min(root.begin(), root.end());
}

리팩토링

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

using namespace std;

bool isConvertable(const string& begin, const string& target)
{
    int count = 0;

    for (int i = 0; i < begin.size(); i++)
    {
        if (begin[i] != target[i])
        {
            count++;
        }
    }

    return count == 1;
}

void DFS(const string& current, const string& target, unordered_map<string,bool>& visited, vector<int>& results, int& count)
{
    if (target == current)
    {
        results.push_back(count);
        return;
    }

    for (const auto& word : visited)
    {
        if (isConvertable(current, word.first) && ! word.second)
        {
            visited[word.first] = true;
            count++;
            DFS(word.first, target, visited, results, count);
            count--;
             visited[word.first] = false;
        }
    }

}

int solution(string begin, string target, vector<string> words)
{
    vector<int> results;

    unordered_map<string, bool> visited;
    for (const string& word : words)
    {
        visited[word] = false;
    }

    int count = 0;

    DFS(begin, target, visited, results, count);

    return (results.empty()) ? 0 : *min(results.begin(), results.end());
}

바뀐 부분:

• roots를 solution 안으로
• roots의 이름을 results로
• DFS가 results를 인자로 받는다.
• 선언 순서를 바꿈

1차 풀이와 바뀐 점

• 1차 풀이 때에는 매번 isConvertable을 돌리기가 싫어서 한번만 돌리도록 convertMap을 만들었다.
• 그에 따라 indexesMap도 만들었고 구조가 복잡해져서 꼬였다.
• 단어의 길이가 3~10 사이었으니 굳이 하지 않아도 되었음
• 퍼포먼스 신경 << 정확도 신경. 단순한 로직으로 정확도를 맞추고 난 후 퍼포먼스를 신경써야하면 쓰자

3차 풀이 (BFS)

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

using namespace std;

bool isConvertable(const string& begin, const string& target)
{
    int count = 0;

    for (int i = 0; i < begin.size(); i++)
    {
        if (begin[i] != target[i])
        {
            count++;
        }
    }

    return count == 1;
}

int solution(string begin, string target, vector<string> words)
{
    int count = 0;

	queue<string> q;
    q.push(begin);

    int level = 0;
    int levelNum = 1;

    while (!q.empty())
    {
        string current = q.front();
        q.pop();

        if (current == target)
            return level;

        if (level > words.size() + 1)
            return 0;

        for (const auto& word : words)
        {
            if (isConvertable(word, current))
            {
                q.push(word);
            }
        }

        levelNum--;

        if (levelNum <= 0)
        {
            level++;
            levelNum = q.size();
        }

    }
    
    return 0;
}

 

Review

1️⃣퍼포먼스 신경 << 정확도 신경. 단순한 로직으로 정확도를 맞추고 난 후 퍼포먼스를 신경써야하면 쓰자