Programmers / BFS, DFS / 단어 변환

< 문제링크 >

https://www.welcomekakao.com/learn/courses/30/lessons/43163

< 풀이 >

1. 최소 변환을 구해야하므로 BFS 기법으로 탐색

2. cur(현재단어) = begin 부터 시작해서 단어 리스트를 조사해서 변환 가능한 문자열들을 모두 큐에 추가

=> 이 때, 큐의 요소는 (단어, 단계수) 형태로 저장

3. target 단어가 되거나 큐가 빌 때(모든 단어를 탐색 완료)까지 2의 과정 수행

4. 만약 마지막 조사한 단어가 target이 아니면, 모든 단어를 탐색하고 빠져나온 경우이므로 answer = 0

4-else. target 단어이면 cur.second에 단계수가 있으므로 answer=cur.second

< 코드 >

#include <string>
#include <vector>
#include <queue>
using namespace std;

// a가 b로 변환 가능한가? => a와 b가 다른 단어가 1개 인가?
bool is_correct(string a, string b)
{
    int num = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) num++;
        // 다른 단어가 2개 이상이면 변환 불가
        if (num > 1) return false;
    }
    // 두 문자열이 같은 경우는 없으므로 체크하지 않아도 됨
    return true;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    queue<pair<string, int>> que;
    vector<bool> visited(words.size());
    // 현재 조사중인 단어 (단어, 단계수)
    pair<string, int> cur;
    que.push({ begin, 0 });
    do {
        cur = que.front();
        que.pop();
        for (int i = 0; i < words.size(); i++) {
            // 이미 조사했으면 pass
            if (visited[i]) continue;
            // 변환 가능하면 다음 조사 단어 큐에 추가
            if (is_correct(cur.first, words[i])) {
                que.push({ words[i], cur.second + 1 });
                visited[i] = true;
            }
        }
    } while (!que.empty() && cur.first != target);
    // 모든 단어를 다 조사했는데 일치하지 않으면 변환 불가능
    if (cur.first != target) answer = 0;
    // cur.second가 단계수를 가지고 있으므로 답
    else answer = cur.second;
    return answer;
}