https://programmers.co.kr/learn/courses/30/lessons/43163
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> WORDS;
int Depth(0);
int chk[50] = { 0, };
int Answer(99999999);
void dfs(string target, string s, int depth, int answer)
{
for (int i = 0; i < WORDS.size(); i++)
{
if (target == s)//일치하는 경우
{
if (Answer > answer) Answer = answer;
return;
}
}
for (int i = 0; i < WORDS.size(); i++)
{
int flag(0);
for (int j = 0; j < s.size(); j++)
{
if (chk[i] == 0)
{
if (WORDS[i][j] != s[j]) flag++;
if (flag == 1 && j == s.size() - 1)//일치 안하는게 1개인 경우
{
chk[i] = 1;
dfs(target, WORDS[i], depth + 1, answer + 1);
chk[i] = 0;
}
}
}
}
}
int solution(string begin, string target, vector<string> words) {
int answer = 0;
sort(words.begin(), words.end(), [](string a, string b) {
return a < b;
});
for (int i = 0; i < words.size(); i++)
{
WORDS.emplace_back(words[i]);
}
Depth = words.size();
dfs(target, begin, 0, 0);
if (99999999 == Answer) return 0;
answer = Answer;
return answer;
}
int main()
{
string begin = "hit";
string target = "cog";
vector<string> vTemp = { "hot","dot","dog","lot","log","cog" };
int iTemp = solution(begin, target, vTemp);
return 0;
}
전형적인 DFS문제이다.
문제의 조건에서는
if (WORDS[i][j] != s[j]) flag++;
if (flag == 1 && j == s.size() - 1)//일치 안하는게 1개인 경우
{
chk[i] = 1;
dfs(target, WORDS[i], depth + 1, answer + 1);
chk[i] = 0;
}
이부분 신경쓰면서 하면 된다.