프로그래머스 레벨3 단어 변환

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

 

서론

분류는 DFS/BFS

DFS를 이용한 완전탐색으로 구현

 

---

풀이

우선 예제2외 같은 예외를 처리해야한다.

words에 target과 같은 문자열이 없으면 0을 리턴한다.

 

wrods에 target과 같은 문자열이 있으면 begin을 target이 될 때까지 DFS를 실행하는 완전탐색으로 최초 문자열이 변할 수 있는 모든 경우의 수를 탐색한다.

현재 문자열(최초에는 begin)을 words의 문자열들과 비교해서 변환 가능하면 DFS를 계속 이어간다.

 

아래는 현재 문자열이 선택한 words의 문자열로 변환 가능한지 확인하는 문자열 비교함수

두 문자열의 같은 문자(순서도 같은) 개수가 문자열의 길이-1이면 변환가능하므로 true를 리턴 

bool stringCompare(string a, string b) {
	int sum = 0;
	int len = a.length();
	for (int i = 0; i < len; i++) {
		if (a[i] == b[i]) sum++;
	}
	if (sum == len - 1) return true;
	else return false;
}

 

DFS

void dfs(int idx, string cur, string target, vector<string> &words) {
	if (cur.compare(target) == 0) { // 현재 문자열이 target과 같으면 answer와 dfs의 탐색깊이(몇단계만에 왔는지)를 비교
		answer = min(answer, idx);
		return;
	}

	for (int i = 0; i < wordsSize; i++) { // words의 문자열 중 변경하능한 문자열을 찾아서 탐색을 이어간다
		if (visited[i] == 0 && stringCompare(words[i], cur) == true) { // 문자열 비교함수가 true면 변경가능
			//cout<<cur<<endl;
			visited[i] = 1;
			dfs(idx + 1, words[i], target, words);
			visited[i] = 0;
		}
	}
	return;
}

 

---

구현

// c++
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int visited[50];
int answer = 0x7f7f7f7f;

bool stringCompare(string a, string b) {
	int sum = 0;
	int len = a.length();
	for (int i = 0; i < len; i++) {
		if (a[i] == b[i]) sum++;
	}
	if (sum == len - 1) return true;
	else return false;
}

void dfs(int idx, string cur, string target, vector<string> &words) {
	if (cur.compare(target) == 0) {
		answer = min(answer, idx);
		return;
	}

	int vSize = words.size();
	int len = words[0].length();
	for (int i = 0; i < vSize; i++) {
		if (visited[i] == 0 && stringCompare(words[i], cur) == true) {
			//cout<<cur<<endl;
			visited[i] = 1;
			dfs(idx + 1, words[i], target, words);
			visited[i] = 0;
		}
	}
	return;
}

int solution(string begin, string target, vector<string> words) {
	bool findTarget = false;
	for (int i = 0, size = words.size(); i < size; i++) {
		if (target.compare(words[i]) == 0) findTarget = true;
	}
	if (findTarget == false) return 0;

	dfs(0, begin, target, words);
	return answer;
}