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

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

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool visit[51];
int ans = 10000;

bool CanChange(string a, string b){
    int res = 0;
    for(int i = 0; i < a.size(); i++){
        if(a[i] != b[i])
            res++;
    }
    
    if(res == 1)
        return true;
    else
        return false;
}

void DFS(string& start, string& end, int count, vector<string>& words){
    for(int i = 0; i < words.size(); i++){
        if(CanChange(start, words[i])){
            if(words[i] == end){
                ans = min(ans, count + 1);
                return;
            }
            
            if(!visit[i]){
                visit[i] = true;
                DFS(words[i], end, count + 1, words);
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    DFS(begin, target, 0, words);
    
    if(ans == 10000)
        ans = 0;
    return ans;
}

---

 코드에서 넣어야 할건

    - 다음 단어와 1글자만 다른지 검사하기

    - 값을 계산할 count

 일단 이 2가지로 생각하고 문제를 풀이했는데 처음에 테스트케이스 1개가 잘 실행이 안되었습니다.

void DFS(string& start, string& end, int count, vector<string>& words){
    for(int i = 0; i < words.size(); i++){
        if(CanChange(start, words[i])){
            if(words[i] == end){
                ans = min(ans, count + 1);
                return;
            }
            
            if(!visit[i]){
                visit[i] = true;
                DFS(words[i], end, count + 1, words);
            }
        }
    }
}

 위 DFS 함수에서 목표 단어와 같아지는걸 체크하는 부분을 포문 밖으로 넣으니 값이 원하는대로 나오지 않았습니다. 그래서 위처럼 포문 안에 넣어주니 잘 되었습니다. 이미 결과에 도달한 것이기 때문에 if(!visit[i])보다 비교하는게 먼저 나오게 했습니다. 결과적으로 위 로직을 이용해 dfs를 실행하게 되었습니다.