[Lv.3] 단어 변환

출처.프로그래머스

 

기본적인 DFS방식으로 문제를 풀면되고, 어렵지않다.

begin과 words의 요소를 비교하는 방식은 단순히 처음부터 한글자씩 비교해 가면서 다른글자숫자를 셌다.

diffCnt가 1일 경우에 vector에서 해당 위치를 삭제하고 동일하게 DFS를 반복한다.

 

DFS가 종료된 이후에는 동일한 위치에 복구하고 다음 위치를 비교하는 식으로 구현했다.

구현사항은 주석 참고!

#include <string>
#include <vector>

using namespace std;

int answer = 0;
string g_target;

void DFS(string begin, vector<string>& words, int count) {
    if (begin == g_target) { // 탈출문!
        if (answer > count)
            answer = count; // count의 최소값 저장
        
        return ;
    }
    
    for (vector<string>::iterator iter = words.begin() ; iter != words.end() ; iter++) {
        size_t diffCnt = 0;
        for (size_t i = 0 ; i < g_target.length() ; i++) {
            if (begin.at(i) != iter->at(i))
                diffCnt++;
            
            if (diffCnt > 1)
                break;
        }
        
        if (1 == diffCnt) {
            string peek = *iter; // 현재 iterator 값 저장.
            words.erase(iter); // vector에서 삭제
            DFS(peek, words, count+1);
            words.insert(iter, peek); // DFS 종료 후 vector값 복구
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    g_target = target; // target을 전역변수에 저장
    
    vector<string>::iterator iter;
    
    for (iter = words.begin() ; iter != words.end() ; iter++) {
        if (*iter == target)
            break;
    }
    
    // 위 반복문에서 vector에 target이 없는 경우를 체크하는 조건문
    if (iter != words.end()) {
        answer = 100; // vector words의 최대가 50이기 때문에 answer는 대충 큰 값인 100을 잡음
        DFS(begin, words, 0);
    }
    
    return answer;
}