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

---

입력으로 문자열들이 주어져서 선뜻 그래프를 다루는 문제라고 떠오르지 않는다. 각 단어들의 관계를 그래프로 생각할 수 있다면 쉽게 풀 수 있다.

각 단어에서 '한글자'만 다르다면 변환할 수 있다. 이 조건에 맞는 단어들을 그래프로 연결해보자.

첫단어(begin)인 hit은 ["hot", "dot", "dog", "lot", "log", "cog"] 중 hot과 연결할 수 있고, hot은 dot, lot과 연결된다. 이런식으로 모든 단어를 연결하면 다음과 같은 그래프가 나온다.

이처럼 그래프라고 생각하고 최단거리를 구하면 문제가 간단해진다.단어는 "hit" -> "hot" -> "dot" -> "dog" -> "cog" 순으로 변환된다.

---

아래는 bfs를 활용한 코드이다.

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

using namespace std;

bool promise(string &a, string &b)
{
    int diff = 0;
    for (size_t i = 0; i < a.length(); ++i)
        if (a[i] != b[i])
            ++diff;
    
    if (diff == 1)
        return true;
    return false;
}

int solution(string begin, string target, vector<string> words)
{
    map<string, int> dist;
    
    queue<string> q;
    q.push(begin);
    dist[begin] = 0;
    
    while (!q.empty())
    {
        string here = q.front();
        q.pop();
        
        if (here == target)
            return dist[here];
        
        for (auto there : words)
        {
            if (dist[there] || !promise(here, there))
                continue;
            
            dist[there] = dist[here] + 1;
            q.push(there);
        }
    }
    
    return 0;
}

위 코드와 다르게 처음부터 간선(edge)을 만들어 주거나, std::map으로 선언한 dist를 std::vector로 선언할 수도 있다.