Programmers: 단어 변환

문제

• 문제: https://programmers.co.kr/learn/courses/30/lessons/43163
• 분류: DFS/BFS

알고리즘

• 만약 인풋 벡터에 답[Target]이 없으면 0 리턴
• DFS 탐색 시작
  • 만약 현재 값과 답이 같으면 깊이 갱신 후 리턴
  • 아니라면 다음을 진행
    • 인풋 벡터를 순회하면서
    • 만약 현재 '단어'와 인풋 백터 안에 있는 단어의 차이가 '1'이라면
    • DFS 재귀[Depth + 1]

코드

#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;

int min_number = INT_MAX;

bool is_difference_one(string& target, string& target_two) {
    int differ = 0;
    for (int i = 0; i < target.length(); i++) {
        if (target[i] != target_two[i]) {
            differ++;
        }
    }

    return (differ == 1);
}

void do_dfs(string work, string& target, vector<string>& vec_target, vector<bool>& used_vector, int depth) {
    if (work == target) {
        min_number = min(min_number, depth);
        return;
    }

    for (int i = 0; i < vec_target.size(); i++) {
        if (is_difference_one(work, vec_target[i]) && used_vector[i] == false) {
            used_vector[i] = true;
            do_dfs(vec_target[i], target, vec_target, used_vector, depth+1);
            used_vector[i] = false;
        }
    }
}

int solution(string begin, string target, vector<string> vec_target) {
    if (find(vec_target.begin(), vec_target.end(), target) == vec_target.end()) return 0;
    vector<bool> used_vector(vec_target.size(), false);
    do_dfs(begin, target, vec_target, used_vector, 0);
    return min_number;
}