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

분류 : dfs/bfs

 

요구사항

최저의 이동으로 str을 target으로 변환시키기

 

풀이

최저 이동으로 target으로 변환시켜야 된다

조건은 now->next로 이동할때 단어가 1개 달라야지 이동할 수 있다는 것이다.

이 조건만 처리해주면 일반적인 dfs로 풀이하면 된다

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<string> v;
string m;
int ans = 987654321;
int visit[100];
int check(string a, string b) {
	int j = 0;
	int i = 0;
	int cnt = 0;
	while (a[i]) {
		if (a[i++] != b[j++]) {
			cnt++;
		}
		if (cnt == 2) {
			break;
		}
	}
	return cnt;
}
void dfs(string str, int num) {
	if (str == m) {
		ans = min(ans, num);
	}
	
	for (int i = 0; i < v.size(); i++) {
		if (visit[i] == 0) {
			if (check(str, v[i]) == 1) {
				visit[i] = 1;
				dfs(v[i], num + 1);
				visit[i] = 0;
			}
		}

	}
}
int solution(string begin, string target, vector<string> words) {
	int answer = 0;
	m = target;
	v = words;
	cout << m << endl;
	dfs(begin, 0);
	if (ans == 987654321)
		ans = 0;
	else
		answer = ans;
	return answer;
}