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

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/43163
알고리즘 : bfs

핵심

그래프 탐색, 각 노드를 방문하여 가능한 노드에서 계속해서 진행
방문해야 할 q와 방문한 리스트를 관리
이때 방문해야 할 q에서 현재 몇번째 스탭인지도 관리가 필요함.

#include <algorithm>
#include <queue>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

// 단어가 한 글자 차이인지 확인하는 함수
bool is_one_diff(string current_word, string diff_word) {
    int diff_count = 0;
    for (int i = 0; i < current_word.size(); ++i) {
        if (current_word[i] != diff_word[i])
            diff_count++;

        if (diff_count > 1) {
            return false;
        }
    }

    return true;
}

int solution(string begin, string target, vector<string> words) {
    if (find(words.begin(), words.end(), target) == words.end()) {
        return 0;
    }

    // 방문해야할 큐
    std::queue<std::pair<std::string, int>> q;
    // 방문 한 큐
    std::vector<string> visited;

    // 처음 시작은 begin 부터
    q.push({begin, 0});
    visited.emplace_back(begin);

    while (q.empty() == false) {
        auto [current_word, steps] = q.front();
        q.pop();

        if (current_word == target) {
            return steps;
        }
        for (const auto &word : words) {
            // find(visited.begin(), visited.end(), word) == visited.end() => 한번도 방문한적 없는 word
            if (find(visited.begin(), visited.end(), word) == visited.end() && is_one_diff(current_word, word) == true) {
                // 해당 조건에 충족하면 현재 word에서 한글자만 틀린 다음 word로 넘어 갈 수 있음.
                // 따라서 q에 추가, vistied에도 추가
                q.push({word, steps + 1});
                visited.emplace_back(word);
            }
        }
    }

    return 0; // 변환할 수 없는 경우
}