[프로그래머스] 단어 변환(c++)

문제 접근

1. 한번에 한 개의 알파벳만 변경가능
2. words에 있는 단어로만 변경 가능

dfs문제이다.
현재 word와 words에 있는 단어들 중 하나를 선택해 비교하여, 한개의 알파벳만 다르다면, 변경을 하고, 다음 단계로 넘기면 된다.
하나의 node를 탐색할 때마다 현재의 word가 target과 일치하는 지 구하면 된다.

코드 구현(c++)

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;
int check[51];
int result = 987654321;
bool oneAlphaDif(string str1 ,string str2){
    int cnt = 0;
    for(int i = 0 ; i < str1.length() ; i++){
        if(str1[i] != str2[i]) cnt++;
    }
    if(cnt == 1) return true;
    else return false;
}
void dfs(int cnt, string word, string target, vector<string> words){
    if(word == target){
        result = min(result, cnt);
    }
    else{
        for(int i = 0 ; i < words.size() ; i++){
            if(!check[i] && oneAlphaDif(word, words[i])){
                check[i] = true;
                dfs(cnt + 1, words[i], target, words);
                check[i] = false;
            }
        }
    }
}
int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    memset(check, false, sizeof(check));
    dfs(0, begin, target, words);
    if(result == 987654321) result = 0;
    answer = result;
    return answer;
}