programmers DFS/BFS | 단어 변환

깊이 우선 탐색 문제
코딩테스트 연습 - 단어 변환 | 프로그래머스

#include <iostream>// need to be delete before submit
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

bool ft_can_trans(string before, int i, vector<string> words) {
    if (before.length() != words[i].length()) {
        return false;
    }
    for (int j = 0; j < before.length(); j++) {
        string temp = words[i];
        temp[j] = before[j];
        if (before == temp) {
            return (true);
        }
    }
    return (false);
}

// 
int dfs(int deep, vector<bool> visited, string before, string target, vector<string> words) {
    vector<int> store_deep;
    int temp;
    
    if (before == target)
        return (deep);

    for (int i = 0; i < words.size(); i++) {
        if (visited[i] == false && ft_can_trans(before, i, words) == true) {
            visited[i] = true;
            temp = dfs(deep + 1, visited, words[i], target, words);
            if (temp > 0) {
                store_deep.push_back(temp);
            }
        }
    }
    if (store_deep.size() != 0)
        return (*min_element(store_deep.begin(), store_deep.end()));
    return (0);
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;

    // https://cplusplus.com/reference/vector/vector/vector/
    // false를 기본값으로하는 단어 갯수만큼의 bool 벡터 생성. 
    vector<bool> visited(words.size(), false);
    answer = dfs(0, visited, begin, target, words);
    return answer;
}

int main() {
    string begin = "hit";
    string target = "cog";
    int answer;

    //string vector initialization
    //https://www.delftstack.com/ko/howto/cpp/how-to-initialize-a-vector-in-cpp/
    vector<string> ex1 = {"hot", "dot", "dog", "lot", "log", "cog"};
    answer = solution(begin, target, ex1);
    cout << "ex1: " << answer << endl;

    vector<string> ex2 = {"hot", "dot", "dog", "lot", "log"};
    answer = solution(begin, target, ex2);
    cout << "ex2: " << answer << endl;
}