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

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

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

 

문제풀이

dfs를 이용하여 현재 단어와 한 개의 알파벳만 차이나는 words를 찾아 이동시킨다.

 

소스코드

#include <string>
#include <vector>

using namespace std;
int visited[50] = { 0, };
int answer = 987654321;
bool checkChangeWord(string s1, string s2) {
	int diffCount = 0;
	for (int i = 0; i < s1.length(); i++) {
		if (s1[i] != s2[i]) {
			diffCount++;
			if (diffCount > 1) {
				return false;
			}
		}
	}
	return diffCount == 1 ? true : false;
}
void solve(string cur, string target, vector<string> words, int depth)
{
	if (cur == target) {
		if (answer > depth) {
			answer = depth;
		}
		return;
	}
	if (answer < depth) {
		return;
	}

	for (int i = 0; i < words.size(); i++) {
		if (visited[i] == 0 && checkChangeWord(cur, words[i])) {
			visited[i] = 1;
			solve(words[i], target, words, depth + 1);
			visited[i] = 0;
		}
	}
}

int solution(string begin, string target, vector<string> words) {
	solve(begin, target, words, 0);
	return answer == 987654321 ? 0 : answer;
}