|| 문제설명 ||
- 두 개의 단어 begin, target과 단어의 집합 words가 있다.
- 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 한다.
- 한 번에 한 개의 알파벳만 바꿀 수 있다.
- words에 있는 단어로만 변환할 수 있다.
- 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성하라.
- begin : 시작 단어
- target : 마지막 단어
- words : 단어의 집합
_ 각 단어 : 알파벳 소문자
_ 각 단어의 길이 : 3 이상 10 이하, 모든 단어의 길이는 같다
_ words : 3개 이상 50개 이하의 단어, 중복X
_ begin != target
_ 변환할 수 없는 경우에는 0를 return
|| 문제해결방법 ||
- 각 단어의 자리를 비교해서 차이가 1 발생하는 단어들로만 재귀함수 호출
- 각 경우를 비교해서 가장 적은 과정을 return
|| 코드 ||
[2020.08.29] 실패
#include <string>
#include <vector>
using namespace std;
int answer = 100;
void dfs(string begin, string target, vector<int> chk, vector<string> words, int p) {
for(int i=0; i<words.size(); i++) {
int cnt = 0;
if(chk[i]){
for(int j=0; j<words[0].size(); j++) {
if(begin[j] != words[i][j]) cnt++;
}
}
if(cnt == 1) {
if(begin == target) {
if(answer > p) answer = p;
return;
}
chk[i] = 0;
dfs(words[i], target, chk, words, p+1);
chk[i] = 1;
}
}
}
int solution(string begin, string target, vector<string> words) {
vector<int> chk(words.size(), 1);
dfs(begin, target, chk, words, 0);
if (answer == 100) answer = 0;
return answer;
}
- if(begin == target) 의 위치 설정 오류
위치를 그대로 하려면 begin -> words[i]으로 바꾸고 p → p+1로 고쳐서 return 해야함
[2020.08.29] 성공
- 애초에 함수의 시작부분으로 옮겨 바로 return
#include <string>
#include <vector>
using namespace std;
int answer = 100;
void dfs(string begin, string target, vector<int> chk, vector<string> words, int p) {
if(begin == target) {
if(answer > p) answer = p;
return;
}
for(int i = 0; i < words.size(); i++) {
if(chk[i]){
int cnt = 0;
for(int j = 0; j < words[0].size(); j++) {
if(begin[j] != words[i][j]) cnt++;
}
if(cnt == 1) {
chk[i] = 0;
dfs(words[i], target, chk, words, p+1);
chk[i] = 1;
}
}
}
}
int solution(string begin, string target, vector<string> words) {
vector<int> chk(words.size(), 1);
dfs(begin, target, chk, words, 0);
if (answer == 100) answer = 0;
return answer;
}