[DFS 순열] 프로그래머스 단어 변환 C++

 

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

#include <string>
#include <vector>
#define MAX 51

using namespace std;

int res = MAX;
bool check[MAX];

void dfs(string begin, string target, vector<string> words, int ans) {
	if (target == begin) {
		res = min(res, ans);
		return;
	}

	for (int i = 0; i < words.size(); i++) {
		int cnt = 0;
		for (int j = 0; j < words[i].size(); j++) {
			if (begin[j] != words[i][j]) cnt++;
			if (cnt >= 2) break;
		}
        
		// 다른 알파벳이 하나여야 수정 가능
		if (cnt == 1){
			if (!check[i]) {
				check[i] = true;
				dfs(words[i], target, words, ans + 1);
				check[i] = false;
			}
		}
	}
}

int solution(string begin, string target, vector<string> words) {
	dfs(begin, target, words, 0);
	if (res == MAX) res = 0;
	return res;
}