단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163

기본적인 백트래킹 문제이다.

#include <iostream>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
bool use[51] = { false, };
 
int MIN = 0;
 
bool check(string s, string g)
{
    int other = 0;
 
    for (int i = 0; i < s.length(); i++)
        if (s.at(i) != g.at(i))
        {
            ++other;
 
            if (other >= 2) return false;
        }
 
    return true;
}
 
void simulation(string begin, string target, vector<string> words, int cnt)
{
    if (begin == target)
    {
        MIN = min(MIN, cnt);
 
        return;
    }
 
    for (int i = 0; i < words.size(); i++)
        if (!use[i] && check(begin, words.at(i)))
        {
            use[i] = true;
 
            simulation(words.at(i), target, words, cnt + 1);
 
            use[i] = false;
        }
}
 
int solution(string begin, string target, vector<string> words) 
{
    int answer = 0;
 
    MIN = 2e9;
 
    simulation(begin, target, words, 0);
 
    answer = MIN;
 
    if (answer == 2e9) answer = 0;
 
    return answer;
}
 
int main(void)
{
    string begin, target;
 
    vector<string> words = { "hot", "dot", "dog", "lot", "log", "cog" };
 
    begin = "hit";
 
    target = "cog";
 
    cout << solution(begin, target, words) << '\n';
 
    return 0;
}