프로그래머스 Level3 - 단어 변환 C++

이 문제는 오타 때문에 고생했던 문제다....

 

begin단어에서 하나만 다른 걸 찾아 나가면 되는데, 재귀함수로 풀면 쉽게 풀린다.

방문체크/변환 가능 여부를 따진다.

그리고 단계마다 1씩 더해가면서 재귀 돌리면 끝~!

 

답은

최소 단계 찾기,words의 최대 수 50이니까 answer 초기값을 51로 설정해주고, 나중에 이 51이 그대로면 0을 반환한다.

 

 

#include <string>
#include <vector>
 
using namespace std;
 
int answer=51;
 
void dfs(string begin, string target, vector<string>& words, vector<bool>& visit,int cnt){
    //같은 단어 찾음
    if(begin==target){
        //최소 단계를 answer에
        answer = min(cnt,answer);
        return;
    }
    
    
    for(int i=0;i<words.size();i++){
        int check=0; //알파벳 하나만 다른지 검사
 
        //아직 확인 안 한 단어면
        if(!visit[i]){
            //몇개가 다른지 check
            for(int j=0;j<begin.length();j++){
                if(begin[j]!=words[i][j]) check++;
            }
                
            //하나만 다르면 바꿀 수 있음
            if(check==1){
                visit[i]=true;
                dfs(words[i],target,words,visit,cnt+1);
                visit[i]=false;
            }
        }
    }
    
}
 
 
int solution(string begin, string target, vector<string> words) {
    
    vector<bool> visit(words.size(),false);
    
    dfs(begin,target,words,visit,0);
    
    if(answer==51) answer=0;
    
    return answer;
}