[프로그래머스] #단어변환(DFS)

 

프로그래머스 #DFS - 단어변환

https://programmers.co.kr/learn/courses/30/lessons/43163?language=cpp

 

사용한 개념

 

DFS 문제입니다. 

탐색가능한 단어를 찾고, 다시 탐색한 단어으로 탐색가능한 단어를 찾고.. 이 과정에서 일전에 지나왔던 단어는 다시 탐색하지 않습니다! 왜냐..무한 재귀를 돌기 때문이죠..또한, 최소탐색횟수를 구하는 문제에 철학에도 맞지 않습니다. 

저는 아래와 같은 프로세스로 해당 문제를 해결했습니다.

 

1. 탐색 가능한 단어찾기

(알파벳 1개만 다른경우만 가능 : 중복체크를 방지하기 위해 한번 찾은 알바벳을 의미 없는 문자로 대체)

2. 탐색 가능한 단어가 일전에 탐색한 단어인지 체크(새로운 단어인 경우만 탐색)

3. 타켓을 구하면, 탐색 횟수를 저장한다.

4. 시작 탐색단어를 새로 갱신하고, 탐색 횟수 증가(n+1)

5. 1-4 반복하다가..타켓단어를 찾으면 dfs 종료.

 

 

아래는 전체 소스입니다.

 

#include
#include
#include   
#include

 using namespace std;
vector ans;
void dfs(string begin, string target, vector words, string history, int n) {
	for (int i = 0; i < words.size(); i++) {
		string obj = words.at(i);

		//탐색 가능한 단어 구하기
		int same = 0;
		string tmp = obj;
		for (int j = 0; j < begin.size(); j++) {
			for (int k = 0; k < obj.size(); k++) {
				if (begin.at(j) == tmp.at(k)) {
					tmp.at(k) = '.'; //중복체크 방지
					same++; 
					break;
				}
			}
		}
		//1개 알파벳만 다른경우
		if (same == begin.size()-1) {
			//탐색 가능한 단어가 일전에 탐색한 단어인지 체크(새로운 단어인 경우만 탐색)
			if (history.find(obj) == string::npos) {
				if (target == obj) {//타켓을 구하면, 탐색 횟수를 저장한다.
					ans.push_back(n+1);
					return;
				}
                //begin은 다음 탐색 단어!, 탐색시 탐색 횟수 증가(n+1)
				dfs(obj, target, words, history + " " + obj, n + 1);
			}
		}
	}
}
int solution(string begin, string target, vector words) {
    int answer = 0;
    dfs(begin, target, words, begin, 0);
    if (!ans.empty()) {
	    sort(ans.begin(), ans.end());
        answer = ans.at(0);
	}
    return answer;
}