[프로그래머스] 단어 변환

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

 

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.

2. words에 있는 단어로만 변환할 수 있습니다.

 

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

---

C++ 문제 풀이

#include <string>
#include <vector>

using namespace std;
int minCount;
string targetS;

bool diffcheck(string a, string b) { //문자 한 개만 다른지 체크
	int count = 0;
	for (int i = 0; i < a.length(); i++) {
		if (a[i] != b[i])
			count++;
	}
	if (count == 1)
		return true;
	else
		return false;
}

void change(int count, string currentS, vector<string>leftwords) {
	if (diffcheck(currentS, targetS)) {
		if (count < minCount)
			minCount = count;
		return;
	}
	for (int i = 0; i < leftwords.size(); i++) {
		if (diffcheck(currentS, leftwords[i])) {
			vector <string> Newleftwords = leftwords;
			Newleftwords.erase(Newleftwords.begin() + i);
			change(count + 1, leftwords[i], Newleftwords);
		}
	}
}

int solution(string begin, string target, vector<string> words) {
	minCount = 51;
	targetS = target;
	for (int i = 0; i < words.size(); i++) {
		if (target == words[i]) {
			words.erase(words.begin() + i);
			break;
		}
		if (i == words.size() - 1)
			return 0;
	}
	change(0, begin, words);
	if (minCount == 51)
		return 0;
	else
		return minCount + 1;
}

현재 문자에서 하나의 문자만 달라야지 변환할 수 있다는 규칙을 적용하여 DFS로 풀었다.

 

 

 

문제 링크

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

코딩테스트 연습 - 단어 변환 | 프로그래머스