프로그래머스: 단어변환

풀이 :

bool 배열을 이용한(똑같은 단어를 두번 탐색하지 않게 하기위해) dfs 를 구현하였다.

그리고 한글자만 다른 단어로 넘어가게 하였고

index를 비교해 제일 작은 결과값을 저장!

---

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>
using namespace std;
bool v[51];
string t;
int result = 10000;

void dfs(vector<string> &words, string begin, string target, int index){
    if(begin == target){
        if(result> index){
            result = index;
        }
        return;
    }
    if(index >= words.size()){
        return;
    }
    for(int i=0; i<words.size(); i++){
        if(v[i]==true){
            continue;
        }
        int check =0;
        for(int j=0; j<words[i].size(); j++){
            if(words[i][j]!=begin[j]){
                check++;
            }
        }
        if(check==1){
            v[i] = true;
            dfs(words,words[i],target,index+1);
            v[i] = false;
        }
    }    
}


int solution(string begin, string target, vector<string> words) {
    t= target;
    if(words.end()==find(words.begin(), words.end(), target)){
        return 0;
    }

    dfs(words,begin,target,0);
    if(result==10000){ // 10000이면 target까지 갈수 없음을 의미함
        return 0;
    }
    return result;
}