C++ 단어 변환

 

begin에서 target이 될 때까지 DFS탐색을 하면서 총 몇 번에 변환이 완료되는지 구하면 된다.

단어는 오직 한 글자씩만 변할 수 있으니 반복문을 통해서 각각 단어들을 비교해주고

차이가 1이라면 DFS를 재귀 호출해주면 된다.

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
bool vis[51];
int ans = 100000;
 
void DFS(string cur, string target, vector<string> ar, int cnt, int n, int sum) {
    if (cur == target) {
        ans = min(ans, sum);
    }
    if (cnt == n) return;
    
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            vis[i] = true;
            int tmp = 0;
            for (int j = 0; j < ar[i].size(); ++j) {
                if (ar[i][j] != cur[j]) ++tmp;
            }
            if (tmp == 1) DFS(ar[i], target, ar, cnt + 1, n, sum + 1);
            vis[i] = false;
        }
    }
}
 
int solution(string begin, string target, vector<string> words) {
    int answer = 0; 
    DFS(begin, target, words, 0, words.size(), 0);
    
    return ans == 100000 ? 0 : ans;
}