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

프로그래머스

 

• 완전 탐색 문제
• 해당 단어의 사용 여부와 변환 가능 여부를 체크해야함

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// 완전 탐색 문제
// 단어의 사용 여부와 변환 가능 여부를 체크해서 dfs 돌리면 될듯
// target이 words 안에 없을 수도 있음 < 지나칠 뻔

// 방문 여부
bool Used[51] = {false};

// 변환 가능 여부 체크
bool canChange(string str1, string str2) {
    int diff = 0;
    
    // 두 단어 간 다른 알파벳의 개수 구하기
    for(int i = 0; i < str1.size(); i++)
        if(str1[i] != str2[i]) diff++;
    
    // 다른 알파벳의 개수가 1이면 가능 아니면 불가능
    if(diff == 1) return true;
    else return false;
}

// dfs
void dfs(int cnt, string cur, string target, vector<string> words, int &answer) {
    
    // answer보다 cnt가 커지면 더 볼 필요 없음
    if(cnt >= answer) return;
    
    // cur에서 target으로 변환이 가능하면
    if(canChange(cur, target)) {
        answer = min(answer, ++cnt);
        return;
    }
    
    // words 배열 내의 단어들 중
    for(int i = 0; i < words.size(); i++) {
        // 사용한적 없고 변환 가능하면
        if(!Used[i] && canChange(cur, words[i])) {
            
            Used[i] = true;
            // dfs 수행
            dfs(cnt + 1, words[i], target, words, answer);
            
            Used[i] = false;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = INT32_MAX;
    
    // target이 words 안에 있는지 체크
    if(find(words.begin(), words.end(), target) == words.end()) return 0;
    
    // dfs 수행
    dfs(0, begin, target, words, answer);
    
    return answer;
}