C++:: 프로그래머스 < 단어 변환 >

주어진 begin에서 target으로 words안에 있는 단어들을 통해 변환 가능한지 판단하고 가장 적은 회수를 반환하는 문제이다. 크게 어렵지않다.
해당 풀이에서는 역숙으로 구현하였다.

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

int answer = INT32_MAX, n;

bool isChangable(string from, string to) {// 변경 가능한 단어인지 체크
    int diff = 0;
    for (int i=0; i<from.size(); i++) {
        if (from[i] != to[i]) diff++;
    }
    if (diff == 1) return true;
    return false;
}

void dfs(int cnt, string cur, string begin, vector<bool>& vis, vector<string>& words) {
    if (cnt >= answer) return ;// 이미 구한 회수보다 현재 회수가 크거나 같다면
    if (isChangable(cur, begin)) {// 변경가능하면
        answer = min(answer, cnt);
        return ;
    }
    for (int i=0; i<n; i++) {
        if (!vis[i] && isChangable(cur, words[i])) {// 단어를 사용한적없고 변경 가능하면
            vis[i] = true;// 사용체크
            dfs(cnt+1, words[i], begin, vis, words);// dfs
            // 이전에 사용했던 단어였다면 어차피 회수가 더 많아지기 때문에  사용 체크 해제를 굳이 해주지 않아도 된다.
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    if (find(words.begin(), words.end(), target) == words.end()) return (0);// words 에 target이 없으면 변환 불가
    n = words.size();
    vector<bool> vis(n, false);
    dfs(1, target, begin, vis, words);
    return answer;
}