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

< 해설 >

난이도가 높지 않다고 생각했는데 시간초과가 빡센 문제였다. 실제로 벡터를 erase 해서 탐색을 좀 편히 하려고 했건만 erase 할 벡터 찾기, 재귀에 erase한 벡터를 사용해야하니 벡터의 복사비용 등등 때문에 테스트1,2 부터 시간초과가 났다. 그래서 한게 bool 벡터를 따로 둬서 true false 를 체크하면서 탐색했다.

 

현재 인덱스의 벡터의 글자가 begin 글자와 1개만 다른지를 탐색한 뒤, 그게 target 과 동일한지 비교한다. target과 같다면 기존에 갱신되었던 숫자보다 작은지를 비교하여 답으로 넣어준다. target과 동일하지 않다면 다시 DFS를 돈다. 여기서 내 문제가 생긴다.

테스트 1번은 틀리는데 제출하면 올바르게 문제가 해결되는 것이다..

왜 그럴까 하고 vs로도 돌려보면서 확인해봤다.

DFS(_count+1, words[i], target, words, vecBool);

이 줄에서 처음에는 DFS(++_count, words[i], target, words, vecBool); 로 DFS를 탐색했다. 이렇게 탐색을 도니 한번 들어갔다가 return 된 값에는 _count가 +1 이 되어버린 것이었다.... _count 값을 수정하지 않고 인자만 +1 된 채로 넘겼어야 하는 것이다. 중요한걸 알게 되어 참 다행이었다.

 

< 문제 >

 

< 풀이 >

#include <string>
#include <vector>

using namespace std;

int answer = 51;

void DFS(int _count, const string& begin, const string& target, const vector<string>& words, vector<bool> vecBool)
{
    for(int i=0; i< words.size(); i++)
    {
        // words[i]가 1개만 다른지 탐색
        int diffCount = 0;
        for(int length=0; length<words[i].length(); length++)
        {
            if(!vecBool[i] && begin[length] != words[i][length])
                diffCount++;
        }
        if(diffCount == 1) // 1개만 다른것을 만족.
        {
            if(words[i] == target)
            {
                if(_count < answer)
                    answer = _count+1;
                return;
            }
            else
            {
                vecBool[i] = true;
                DFS(_count+1, words[i], target, words, vecBool);
            }
        }  
        // words[i]가 1개만 다른지 만족하지 않는다면 다음거 탐색
    }
}

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