프로그래머스 (미해결) - C++ 단어변환

DFS를 이용하는 문제이다. DFS 함수를 구현할 때, 코드의 flow를 잘 생각하자.

1) words의 값 마다 count 변수를 초기화 해야한다.

2) 매개변수인 begin은, 이전 DFS에서 조건을 만족했던 words[i]이다. 그렇기 때문에 다음 DFS를 수행할 때 words[i]가 begin이 되어 return될 때 까지 DFS 함수를 수행할 것이다. (코드의 flow를 잘 생각하자)

---

1. Solution 코드

#include <string>
#include <vector>

using namespace std;
int answer = 100;


void DFS(string begin, string target, vector<string> words, vector<bool>& useCheck, int count = 0){
    
    for(int i = 0; i < words.size(); i++){
        int count = 0;
        
        for(int j = 0; j < words[i].length(); j++)
            if(!useCheck[i] && begin[j] != words[i][j])
                count++;
        if(count == 1){
            if(target == words[i] && answer > count + 1){
                answer = count + 1;
                return;
            }
        
            useCheck[i] = true;
            DFS(words[i], target, words, useCheck, count + 1);
            useCheck[i] = false;
        }
    }
}

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

 

2. 알아야 할 개념