프로그래머스. 단어변환(c++) / DFS+백트래킹

[메인 로직]

words벡터에 있는 단어들과 비교대상이 되는 단어를 비교하여 한 개의 알파벳만 차이가 나는 지 확인한다. => check함수

그리고 이미 방문했던 단어들은 제외시킨다. => visited배열

이렇게 DFS+백트래킹을 구현하면 된다.

 

#include <string>
#include <vector>
#include <climits>
#include <iostream>
 
using namespace std;
 
int visited[51] = {0, };    
int answer = INT_MAX;
 
// 1개의 글자만 차이나는지 확인
bool check(string s1, string s2){
    if(s1.size()!=s2.size()){
        return false;
    }
    
    int num = 0;
    for(int i=0; i<s1.size(); i++){
        if(s1[i]!=s2[i]){
            num++;
        }
    }
    if(num==1){
        return true;
    }
    
    return false;
}
 
void dfs(string s, int cnt, string target, vector<string> words)
{
    if(s==target){
        answer = min(answer, cnt);
        return;
    }
    
    for(int i=0; i<words.size(); i++){
        if(check(s, words[i]) && !visited[i]){
            visited[i] = true;
            dfs(words[i], cnt+1, target, words);
            visited[i] = false;
        }
    }
}
 
int solution(string begin, string target, vector<string> words) {    
    for(int i=0; i<words.size(); i++){
        if(check(begin, words[i]) && !visited[i]){
            visited[i] = true;
            dfs(words[i], 1, target, words);
            visited[i] = false;
        }
    }
    
    if(answer==INT_MAX){
        answer = 0;
    }
    
    return answer;
}