풀이전략

• 백트래킹으로 풀어보았다!

소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<bool>check(50, false);

int MIN = 51;

//문자열 비교하는 함수 
bool Compare(string& a, string & b)
{
    //한개만 달라야 한다. 
    int cnt = 0;
    
    for(int i = 0; i < a.length(); i++)
    {
        if(a[i] != b[i])
        {
            cnt += 1;
        }
        
        if(cnt >= 2)
            return false;
    }
    
    if(cnt == 0)
        return false;
    
    return true;
}

//백트래킹 하는 함수.
void dfs(vector<string>&word, string& begin, string& target , int cnt)
{
    //종료 조건
    if(target == begin)
    {
        MIN = min(MIN, cnt);
        return;
    }
    
    
    for(int i = 0; i < word.size(); i++)
    {
        if(check[i] == false && Compare(begin, word[i]))
        {
            check[i] = true;
            dfs(word, word[i], target, cnt + 1);
            check[i] = false;
        }
    }
    
    
}


int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    //타겟에 없으면 그냥 종료
    if(find(words.begin(), words.end(), target) == words.end())
        return answer;
    
    
    dfs(words, begin, target, 0);
    answer = MIN;
    return answer;
}