프로그래머스 level -3 코딩 연습-단어 변환
https://programmers.co.kr/learn/courses/30/lessons/43163
코딩테스트 연습 - 단어 변환 | 프로그래머스
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog ->
programmers.co.kr
정답 :
#include <string>
#include <vector>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int dfs(string begin, string target, vector<string> words,int num,int start){
bool bCheck=false;
for(int k=0;k<words.size();k++){
if(target.compare(words[k])==0){
bCheck=true;
break;
}
}
if(!bCheck){
return 0;
}
if(words.size()==num){
return 0;
}
if(begin.compare(target)!=0){
char tmpTarget[target.size()];
target.copy(tmpTarget,target.size());
for(int k=start;k<words.size();k++){
char tmpBegin[begin.size()+1];
begin.copy(tmpBegin,begin.size());
int targetCount=0;
for(int i=0;i<target.size();i++){
if(tmpTarget[i]!=tmpBegin[i]){
targetCount++;
}
}
if(targetCount<=1){
begin=target;
num++;
return num;
}
// cout<<tmpBegin[0];
char tmpWords[words[start].size()];
words[start].copy(tmpWords,words[start].size());
int checkCount=0;
for(int i=0;i<words[start].length();i++){
if(tmpBegin[i]!=tmpWords[i]){
checkCount++;
}
}
// if(checkCount>1){
// return dfs( begin,target, words, num,next);
// }else{
//cout<<checkCount;
int next=start+1;
if(checkCount<=1){
cout<<checkCount;
begin=words[start];
cout<<begin<<endl;
// cout<<checkCount;
if(begin.compare(target)==0){
return num;
}
return dfs( begin,target, words, num+1,next);
}else{
// num--;
return dfs( begin,target, words, num,next);
}
// return dfs( begin,target, words, num,next);
// }
}
}
}
int solution(string begin, string target, vector<string> words) {
int answer = 0;
int num=0;
answer=dfs( begin,target, words, num,0);
return answer;
}
200815
이번에 파라미터 문제로 시간을 낭비를 하였다
다풀어두고 파라미터를 넘길때 생각이 짧았다
#include <string>
#include <vector>
#include<iostream>
using namespace std;
vector<int>data;
int ccn;
int Dfs(string begin, string target, vector<string> words,int answer,int count,int sizes){
if(begin==target){
data.push_back(answer);
return answer;
}
if(sizes==count){
return 0;
}
for(int i=0;i<words.size();i++){
int wordCount=0;
for(int j=0;j<begin.size();j++){
if(begin[j]==words[i][j]){
wordCount++;
}
}
if(wordCount>=begin.size()-1){
string tmpBegin;
tmpBegin=words[i];
vector<string> tmpWord;
tmpWord=words;
tmpWord.erase(tmpWord.begin()+i);
ccn=Dfs( tmpBegin, target, tmpWord,answer+1, count+1,sizes);
}
//
}
return ccn;
}
int solution(string begin, string target, vector<string> words) {
int answer = 0;
int count=0;
answer = Dfs( begin, target, words,answer,count,words.size()-1 );
for(int i=0;i<data.size();i++){
if(data[i]<answer){
answer=data[i];
}
}
return answer;
}
DFS 함수내에 있는 재귀함수 부분에서
처음에 begin과 word를 그대로 넘겼다
문제는 begin=word[j]로 하여 바뀐 상태인데
다음 for문이 돌고 있는상태에서 당연히
바뀐 begin으로 확인하니 hit-> hot으로 바뀐 상태로 for문이 돌아서 원하는 문자들을 비교가 이상해졌다.
그러면 현재 돌고 있는 1번 재귀함수에서 begin이 hot->dot으로 바뀌어 버린다.
ccn=Dfs( begin, target, Word,answer+1, count+1,sizes);그래서 tmpBegin을 만들어서 tmpBegin 파라미터를 따로 보내줫다 또한 word는 삭제하면 1번 재귀함수 내에서 삭제가 되어버려 for문이 돌다가 만다 그래서 tmpWord를 하나 만들어줘서 그 파라미터만 따로 보내준다.
ccn=Dfs( tmpBegin, target, tmpWord,answer+1, count+1,sizes);논리적인 부분에선 틀리지 않앗고 지난번보다 훨씬 간결하게 코드도 만들었다.
문제는 지난번과 마찬가지지로 파라미터를 입력시 재귀함수의 변화에 대한 이해를 더욱 확실히 해야겟다.
기초가 중요하다 !
201006
이번엔 너비 우선 탐색으로 한번 풀어봤다
개념은 이렇다
이런식으로 부모 노드에서 자식 노드가 다음 자식(손자) 노드로 넘어가기전에 미리 현재 자식노드를 전부 검사해준다
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int>saved;
void func(string begin, string target, vector<string> words,int count,vector<bool>bCheck,int size){
if(size<=count){
return;
}
// cout<<begin<<",";
for(int i=0;i<words.size();i++){
int confirm=0;
if(begin==target){
// cout<<count;
// cout<<endl;
saved.push_back(count);
// cout<<saved[0];
i=words.size();
break;
}
for(int j=0;j<begin.size();j++){
if(begin[j]!=words[i][j]){
confirm++;
}
}
if(confirm==1&&bCheck[i]==false){
bCheck[i]=true;
//begin=words[i];
func(words[i], target, words,count+1,bCheck,size);
// cout<<endl;
//break;
}
}
}
int solution(string begin, string target, vector<string> words) {
int answer = 0;
vector<bool>bCheck;
for(int i =0;i<words.size();i++){
bCheck.push_back(false);
}
func(begin, target, words,0,bCheck,words.size());
if(saved.size()>0)
{
sort(saved.begin(),saved.end());
return saved[0];
}
return answer;
}
맨처음 부모노드
func(begin, target, words,0,bCheck,words.size());다음 자식노드들 전부 확인
for(int i=0;i<words.size();i++){
int confirm=0;
if(begin==target){
saved.push_back(count);
i=words.size();
break;
}
for(int j=0;j<begin.size();j++){
if(begin[j]!=words[i][j]){
confirm++;
}
}
if(confirm==1&&bCheck[i]==false){
bCheck[i]=true;
func(words[i], target, words,count+1,bCheck,size);
}
}문자비교 1글자만 다른경우에 바꿔 줄수 있음
for(int j=0;j<begin.size();j++){
if(begin[j]!=words[i][j]){
confirm++;
}
}
if(confirm==1&&bCheck[i]==false){
bCheck[i]=true;
func(words[i], target, words,count+1,bCheck,size);
} bCheck는 현재 자식노드에서 다음 부모가 될 노드를 체크해줌으로써 다음자식(손자) 노드에 중복 방지를 위해 그래서
다음 노드로 넘어가기전에 bCheck를 true로 변경해줌
현재 노드가 타겟노드와 동일시된경우 경로들어온 숫자만큼 count해주며 더이상 그 함수는 자식노드로 갈필요가 없으므로 함수 종료
if(begin==target){
saved.push_back(count);
i=words.size();
break;
}
saved는 모드 target에 도착한 길이를 전부 저장
마지막으로 sort하여 가장 짧은 거리 선택
if(saved.size()>0)
{
sort(saved.begin(),saved.end());
return saved[0];
}만약 target과 일치하는게 없엇을경우 0으로 리턴