프로그래머스 코테 연습 : 단어 변환 [C++] DFS

dfs의 재귀로 풀었다.

 

 

 

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 51;
int answer = 100;
bool visited[MAX];

// 단어 비교해서 하나만 차이나는지 아닌지 체크하는 함수
bool checkDiff(string a, string b){
    int count = 0; 
    for(int i = 0; i<a.length(); i++){
        if(a[i] != b[i]){
            count++;
        }
    }
    
    if(count == 1){
        return true;
    }else{
        return false;
    }
}

// words를 돌며 문자가 하나 차이나면 그 단어를 begin으로 재귀 호출
void dfs(string begin, string target, vector<string> words, bool *visited, int count){

    for(int i=0; i<words.size(); i++){
        if(!visited[i]){
            bool check = checkDiff(begin, words[i]);
            if(check){
                // 첫방문이고 철자가 하나다른 해당 단어가 target과 같다면 count+1해서 answer로 리턴
                if(words[i] == target){
                    answer = min(answer, count+1);
                    return;
                }
                
                // 첫방문이고 철자가 하나다르다면 방문 체크하고 재귀 호출
                visited[i] = true;  // 함수 맨위에서 처리 해줄수도 있지만 
                                    // 맨처음 호출때 begin은 입력값이여서 visited에 자리가 없기때문에                                           // for문안에서 처리
                dfs(words[i], target, words, visited, count + 1);
            }
        }
    }
}



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

    bool visited[MAX] = {false};
    // 처음엔 begin을 넘김 
    dfs(begin, target, words, visited, 0);
    
    if(answer == 100){
        return 0;
    }else{
        return answer;
    }

}