단어변환

108번뇌·2021년 8월 2일
0

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;
			}
            

이부분 신경쓰면서 하면 된다.

profile
내일 아침 눈을 떳을 때, '기대되는 오늘 하루를 만들기 위해' 나는 오늘도 생각하고 고민한다.

0개의 댓글