[ 프로그래머스 단어 변환 (Lv3) ] (C++)

프로그래머스의 단어변환(Lv3) 문제이다.

[ 문제풀이 ]

첫 begin 단어에서 Target단어까지 변환되려면 최소 몇 번을 변환시켜야 하는지 구해야 하는 문제이다.

본인은 이 문제를 완전탐색, 완전탐색 중에서도 너비우선탐색(BFS)를 이용해서 접근해 보았다.

즉 ! 현재 단어에서 , 변환될 수 있는 모든 단어들로 다 변환을 시켜가면서 탐색을 진행하는 것이다.

문제의 조건을 보면, 한 번에 한 개의 알파벳만 바꿀 수 있다고 되어있기 때문에, 이를 탐색조건으로 설정해 주었다.

보다 구체적으로 이야기해보면, 현재 단어와 변환 하려는 단어 2개의 단어를 비교했을 때, 이 2개의 단어간의 틀린 알파벳의 갯수를 이용해서 변환이 가능한지 체크해 주었다.

예를 들어서 "abc" → abd" 인 경우와 , "abc" → "aef" 인 경우를 생각해보자.

현재 "abc"인데, 변환하려는 단어가 "abd"인 경우, 서로 다른 알파벳의 갯수를 Count해보면 '1개'가 나오게 된다.

즉 ! 이 경우에는 변환이 가능한 것이다.

하지만, 현재 "abc"인데, 변환하려는 단어가 "aef"인 경우, 서로 다른 알파벳의 개수를 Count해보면 '2개'가 나오게 된다.

이 경우에는 변환이 불가능한 것이다.

위와 같이 단어들간의 상태를 체크해주면서 BFS탐색을 진행해 주었다. 또한 ! 단어들을 중복적으로 계속 체크하는 상황을 방지하기 위해서 set을 이용해서 string의 Visit을 체크해 주었다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std;
 
bool Check_Change(string A, string B)
{
    int Cnt = 0;
    for (int i = 0; i < A.length(); i++)
    {
        if (A[i] != B[i]) Cnt++;
        if (Cnt >= 2) return false;
    }
    if(Cnt == 1) return true;
    return false;
}
 
int solution(string begin, string target, vector<string> words) 
{
    int answer = 0;
    set<string> Visit;
    queue<pair<string, int>> Q;
    Q.push(make_pair(begin, 0));
    Visit.insert(begin);
 
    while (Q.empty() == 0)
    {
        string Cur = Q.front().first;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Cur == target) return Cnt;
        
        for (int i = 0; i < words.size(); i++)
        {
            string Next = words[i];
            if (Check_Change(Cur, Next) == true && Visit.find(Next) == Visit.end())
            {
                Visit.insert(Next);
                Q.push(make_pair(Next, Cnt + 1));
            }
        }
    }
    return answer;
}