단어 변환 43163

문제

접근 방법

말 그대로 1개의 차이만 있는 단어로 탐색하면 된다고 생각했다. 방문이 가능한 모든 노드를 확인해야 하므로 DFS가 적합하다고 생각했다.

코드

#include <string>
#include <vector>
using namespace std;
int ret = 51;
vector<bool> visted;
void dfs(string cur, string target, vector<string> words, int cnt)
{
    if (cur == target)
    {
        if (ret > cnt)
            ret = cnt;
        return;
    }
    for (int i = 0; i < words.size(); ++i)
    {
        if (visted[i])
            continue;
        int diff = 0;
        for (int j = 0; j < cur.size(); ++j)
        {
            if (cur[j] != words[i][j])
                ++diff;
        }
        if (diff <= 1)
        {
            visted[i] = true;
            dfs(words[i], target, words, cnt + 1);
            visted[i] = false;
        }
    }
}
int solution(string begin, string target, vector<string> words)
{
    visted = vector<bool>(words.size());
    dfs(begin, target, words, 0);
    return ret == 51 ? 0 : ret;
}

풀이

최솟값이므로 나올 수 없는 가장 높은 값을 적어두고 비교해 주는 방식으로 하면 된다.