[c++] 프로그래머스 - 단어변환( Level 3)

문제

코딩테스트 연습 - 단어 변환

 

코드

#include <string>
#include <vector>

using namespace std;

bool visited[1001];
int cnt,ans=9999;

void dfs(string begin,string target,int cnt, vector<string>& words){
    if(begin==target) ans=min(ans,cnt);
    for(int i=0; i<words.size(); i++){
        int check=0;
        for(int k=0; k<words[i].length(); k++){
            if(words[i][k]!=begin[k]) check++;
        }
        if(check==1){
            if(visited[i]) continue;    //이미 탐색했다면 탐색안함.
            visited[i]=true;
            dfs(words[i],target,cnt+1, words);
            cnt--;
        }
    }
}


int solution(string begin, string target, vector<string> words) {

    int answer = 0;

    dfs(begin,target,cnt,words);

    if(ans!=9999) answer=ans;
    return answer;
}

 

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;
int answer=1e9;
unordered_map<string, int>visited;

bool check(string s1, string s2){
    int cnt = 0;
    for(int i=0; i<s1.length(); i++){
        if(s1[i]!=s2[i]) cnt++;
    }
    if(cnt == 1) return true;
    return false;
}


void dfs(string now, string target, vector<string>words, int depth){
    if(now == target){
        answer = min(answer, depth);
        return;
    }
    
    for(int i=0; i<words.size(); i++){
        if(visited[words[i]]) continue;
        if(check(now, words[i])){
            visited[words[i]] = 1;
            dfs(words[i], target, words, depth+1);
            visited[words[i]] = 0;
        }
    }
}
int solution(string begin, string target, vector<string> words) {
    unordered_map<string, int> m;
    for(string s: words) m[s]++;
    if(!m[target]) return 0;
    dfs(begin, target, words, 0);
    return answer;
}