[Programmers] 단어 변환(Lv.3)(C++)

풀이 소요시간 : 15분

간단한 탐색 문제였다. 변화할 수 있는 단어의 세트가 주어졌고, 스펠링 하나만 다른 단어로만 변환이 가능하다. Visit 배열을 두어 중복을 방지하고, Queue를 활용해 BFS를 구현했다. 크게 필요한 접근 방식은 없다.

전체 코드

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

int Visit[50];

//한글자 이하만 다를 경우 True
bool Can_Change(string A, string B) {
    int cnt = 0;
    for(int i = 0; i < A.length(); i++)
    {
        if(A[i] != B[i]) cnt++;
    }
    if(cnt <= 1) return true;
    else return false;
}

int Bfs(string begin, string target, vector<string>& words) {
    queue<pair<string, int>> Q;
    Q.push({begin, 0});
    
    while(!Q.empty())
    {
        string curr = Q.front().first;
        int time = Q.front().second;
        Q.pop();
        
        if(curr == target)
        {
            return time;
        }
        
        for(int i = 0; i < words.size(); i++)
        {
            string next = words[i];
            
            if(Visit[i] == 1) continue;
            if(Can_Change(curr, next) == false) continue;
            Visit[i] = 1;
            Q.push({next, time + 1});
        }
    }
    
    return 0;
}

int solution(string begin, string target, vector<string> words) {
    return Bfs(begin, target, words);
}