프로그래머스_단어 변환

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

코딩테스트 연습 - 단어 변환 | 프로그래머스

해당 문제는 DFS로 해결하였다.

기본적인 DFS였으나 그냥 DFS를 돌리면 터져버린다.

그래서 백트랙킹을 통해서 해결해야 하는데, 이 때 조건은 문자열이 하나가 차이나야 한다는 조건이다.

문자열이 하나가 다를 때 다시 탐색할 수 있다. 문자열이 하나가 다른 조건을 찾을 때 끝까지 다 찾으면 시간복잡도의 측면에서 부하를 줄 수 있으므로 문자열 비교시에 2개 이상이 차이나면 비교를 그만하고 넘어가도록 해야 한다.

 

추가로,  해당 문제에서 words에 있는 단어들을 한 번만 사용해야한다는 조건이 따로 안주어져 있어서 처음에는 문제를 이해하지 못했다. 어쩌면 너무나 당연한 것이라 생각하여 따로 명시를 하지 않았던 게 아닐까 생각한다.

어쨋든 words의 단어들을 한 번만 사용해야 한다는 조건에 맞춰 vector<bool> check를 통해 탐색한 단어들은 재탐색하지 않도록 처리할 수 있다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int ans_glb = 51;
vector<bool> check;
void dfs(vector<string> words, string now, string target, int cnt){
    // 완성 비교
    if(now.compare(target) == 0){
        ans_glb = min(ans_glb, cnt); // 최소값 넣기
        return;
    }
    
    // 갈 수 있는 곳 가기(한개 차이 나면 들어가기)
    for(int i=0;i<words.size();i++){
        // 문자열의 차이가 하나면 변경 가능
        int diff = 0;
        // 한번만 사용
        if(check[i] ==true)
            continue;
        
        for(int j=0; diff<=1 && j<now.size();j++){
            if(now[j] != words[i][j])
                diff++;
        }
        // 하나만 차이나면 변경
        if(diff ==1){
            check[i] = true; // 탐색
            dfs(words, words[i], target, cnt+1);
            check[i] = false; // 탐색 끝
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    
    // 결과 도출 불가
    if(find(words.begin(), words.end(), target) == words.end())
        return 0;
    check.assign(words.size(), false);
    dfs(words, begin, target, 0);
    
    // 답을 찾지 못하면
    if(ans_glb == 51)
        return 0;
    
    // 정답 도출 성공
    return ans_glb;
}