rogramers : 단어 변환 - C++
8866 단어 백트래킹PROGRAMERSlevel3PROGRAMERS
단어 변환
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool isused[51];
int ans;
bool res;
/* 2개의 문자열이 알파벳 1개만 차이나는지 검사 */
bool check(string cur, string target){
int cnt=0;
for(int i=0;i<cur.length();i++)
if(cur[i] != target[i]) cnt++;
if(cnt == 1) return true;
return false;
}
void DFS(int num, string cur, string target, vector<string>& words){
if(check(cur, target)){
ans=min(ans,num+1);
return;
}
for(int i=0;i<words.size();i++)
{
if(isused[i]) continue;
if(!check(cur, words[i])) continue;
isused[i] = true;
DFS(num+1, words[i], target, words);
isused[i] = false;
}
}
int solution(string begin, string target, vector<string> words) {
ans = words.size();
/* Words에 target이 없으면 어차피 못찾으니까 return 0; */
auto it = find(words.begin(), words.end(), target);
if(it == words.end()) return 0;
/* 백트래킹 시작 */
DFS(0, begin, target, words);
return ans;
}
Author And Source
이 문제에 관하여(rogramers : 단어 변환 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/Programers-단어-변환-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <string> #include <vector> #include <algorithm> using namespace std; bool isused[51]; int ans; bool res; /* 2개의 문자열이 알파벳 1개만 차이나는지 검사 */ bool check(string cur, string target){ int cnt=0; for(int i=0;i<cur.length();i++) if(cur[i] != target[i]) cnt++; if(cnt == 1) return true; return false; } void DFS(int num, string cur, string target, vector<string>& words){ if(check(cur, target)){ ans=min(ans,num+1); return; } for(int i=0;i<words.size();i++) { if(isused[i]) continue; if(!check(cur, words[i])) continue; isused[i] = true; DFS(num+1, words[i], target, words); isused[i] = false; } } int solution(string begin, string target, vector<string> words) { ans = words.size(); /* Words에 target이 없으면 어차피 못찾으니까 return 0; */ auto it = find(words.begin(), words.end(), target); if(it == words.end()) return 0; /* 백트래킹 시작 */ DFS(0, begin, target, words); return ans; }
Author And Source
이 문제에 관하여(rogramers : 단어 변환 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/Programers-단어-변환-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)