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

https://programmers.co.kr/learn/courses/30/lessons/43163

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

 

풀이

이 문제는 재귀함수를 이용해 구현한 DFS를 사용하여 풀이하였다.

이때 한개의 알파벳만 바꿔서 변환이 가능한지 확인하는 change()함수를 만들어서 계속 사용한다.

slove()함수를 재귀로 호출하며 DFS를 구현한다.

solve()함수 내에서는

1. 현재 string이 target string과 동일한지 확인해 동일한 경우 min_change와 현재 재귀의 변경 횟수를 비교해 갱신하고 return
2. 동일하지 않은 경우 재귀를 이어간다.
3. words 벡터의 원소들에 대해서 아직 check[]가 0이고 change()값이 1인 경우(아직 변환하지 않았으며 변환 가능한 경우)에 대해서만 변환했음을 나타내는 check[]를 1로 set해주고 재귀 호출을 한다.
4. 재귀를 마치고 돌아오면 다시 check[] 를 0으로 unset해준다.

#include <string>
#include <vector>

using namespace std;

int check[50];
int min_change = 10000;

//변환 가능한지 확인
int change(string from, string to) {
    int cnt=0;
    
    for(int i=0; i<from.length(); i++){
        if(from[i]!=to[i])
            cnt++;
    }
    //불가능
    if(cnt != 1)
        return -1;
    return 1;
}

//DFS
void solve(int cnt, string now, string target, vector<string> words) {
    
    //target과 같아짐
    if(now == target){
        if(cnt < min_change)
            min_change = cnt;
        return;
    }
    
    
    for(int i=0; i<words.size(); i++){
        //이미 변환 or 변환 불가
        if(check[i] != 0 || change(now, words[i]) != 1)
            continue;
        check[i] = 1;
        solve(cnt+1, words[i], target, words);  //다음!
        check[i] = 0;
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    
    solve(0, begin, target, words);
    
    //변환이 아예 불가능
    if(min_change == 10000)
        answer = 0;
    else
        answer =  min_change;
    
    return answer;
}