프로그래머스-단어 변환

문제 링크

1. 문제 접근 과정🧐

1. 현재 단어에서 다음 단어로 변환하면서 타겟 단어가 되는지 보면 되기에 DFS나 BFS로 풀면 되겠다고 판단
2. 해당 단어의 사용 여부(이미 변환했었는지)를 경로 별로 저장하여 진행
3. 한 경로를 사용했다가 DFS 후 false로 돌려놔야 함(백트래킹)
4. 타겟 단어가 되면 그 때의 깊이를 반환하고 최솟값으로 갱신
5. 모두 봤거나 변환을 못한다면 INT_MAX 반환
   
   

2. 시행착오🤯

• 처음에 DFS로 풀었는데 마지막 반환을 제대로 처리하지 못하고 깊이가 단어들의 개수보다 커지면 INT_MAX 반환으로 하였다가 실패했다.
  • 함수에 반환값이 있어야 하며 DFS를 할 때 최솟값으로 갱신해야 한다.
• 오답 코드

#include <string>
#include <vector>
#include <climits>

using namespace std;

int dif_cnt(string s1, string s2){
    int v = 0;
    for(int i = 0; i < s1.length(); i++){
        if(s1[i] != s2[i]) v++;
    }
    return v;
}

int dfs(string cur, string target, vector<string> words, int depth, vector<bool> used){
    if(cur == target) return depth;
    else if(depth >= words.size()) return INT_MAX;
    for(int i = 0; i < words.size(); i++){
        if(dif_cnt(cur, words[i]) == 1 && !used[i]){
            used[i] = true;
            dfs(words[i], target, words, depth + 1, used);
            used[i] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    vector<bool> used(words.size(), false);
    answer = dfs(begin, target, words, 0, used);
    if(answer == INT_MAX) return 0;
    return answer;
}

3. 개선한 코드😄

• 반환값을 넣고 DFS할 때 최솟값으로 갱신하여 해결
  
• 정답 코드

#include <string>
#include <vector>
#include <climits>

using namespace std;

int dif_cnt(string s1, string s2){
    int v = 0;
    for(int i = 0; i < s1.length(); i++){
        if(s1[i] != s2[i]) v++;
    }
    return v;
}

int dfs(string cur, string target, vector<string> words, int depth, vector<bool> used){
    if(cur == target) return depth;
    int ans = INT_MAX;
    for(int i = 0; i < words.size(); i++){
        if(dif_cnt(cur, words[i]) == 1 && !used[i]){
            used[i] = true;
            ans = min(ans, dfs(words[i], target, words, depth + 1, used));
            used[i] = false;
        }
    }
    return ans;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    vector<bool> used(words.size(), false);
    answer = dfs(begin, target, words, 0, used);
    if(answer == INT_MAX) return 0;
    return answer;
}

4. 회고💭

• BFS로 풀려고 하다가 DFS로 푸는 연습을 하기 위해 DFS로 접근하여 풀었다.
• 재귀의 특성을 잘 이해하고 반환값을 생각해야 한다.(해당 문제는 최솟값)
• void가 아닌 함수는 반환값을 반드시 넣어야 한다.
• 재귀 함수가 돌아가는 흐름을 파악하는 연습을 해야겠다.