프로그래머스 (단어 변환, 깊이/너비 우선 탐색(DFS/BFS)) C++

 

DFS가 아니라 BFS 인것 같긴한데 일단 함수명은 이렇게 dfs로 해버렸다. 아닌가... 아직 개념이 확실히 잡히진 않은듯.. 아무튼 DFS와 BFS를 할 때 파라미터로 하나씩 바뀌어서 넘겨지게 되는 것에 Focus를 맞춘다. 그리고 visited가 가장 중요!! 그리고 이 문제의 경우 방문하지 않은 경우의 node를 queue에 모두 넣고 살피는 것이 아니기 때문에 dfs 재귀를 탈출하게 되면 이중 for문 중 nested된 for문에서 visited 한 노드의 visited를 0으로 만들어야 한다는 것이 포인트

 

 

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

using namespace std;

int answer = 100;
string value;
vector<int> visited(50,0);

void dfs(string begin, string target, vector<string> words, int result) {
    
    if(begin == target) {
        if(answer > result) answer = result;
        return ;
    }
    
    // word 배열에 들어있는 개수만큼 반복
    for(int i = 0 ; i < words.size() ; i++) {
        // count 변수는 for문을 돌 때마다 초기화를 해줘야 한다.
        int count = 0;
        
        // words 배열의 단어 크기만큼 반복을 하면서 일치하지 않는 문자의 개수를 세준다.
        for(int j = 0 ; j < words[i].size() ; j++) {
            if(begin[j] != words[i][j]) count++;
        }
        
        // 틀린 문자의 개수가 1개이면 DFS를 실시한다.
        if(count == 1) {
            // 만약 해당 단어를 방문하지 않았으면
            if(visited[i] == 0) {
                // 방문을 하고
                visited[i] = 1;
                // DFS를 진행한다.
                dfs(words[i], target, words, result+1);
                /* 
                DFS를 탈출했다는 것은 begin == target의 상황을 만났고 
                해당 answer에 result 값을 넣었다는 것이다.
                이를 다시 0으로 바꾸는 이유는 이전 begin에서 Spell 이 1개가 다른 단어가
                여러 개 존재하기 때문에 해당하는 단어로도 바뀔 수 있어야 모든 경우의 수를
                탐색하는 경우가 되기 때문이다.
                */
                visited[i] = 0;
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) {

    dfs(begin, target, words, 0);
    
    // 만약 answer가 100이면 result가 바뀌지 않았다는 것이고 바뀔 수 없다는 것
    if(answer == 100) answer = 0;
    
    return answer;
}