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

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/43163

풀이

---

두 개의 단어 begin, target을 한 번에 한 개의 알파벳만 바꿔 주어진 문자열 집합 words의 원소 중 하나로 바꾸는 것을 반복하여 같은 문자로 변환하는 과정 중 가장 짧은 변환 과정을 찾는 문제이다. 따라서 DFS를 통해 words와 하나의 알파벳만 다른 경우의 수를 찾고, 변환하는 과정을 반복하여 최소 변환 과정을 찾는다.

#include <string>
#include <vector>

using namespace std;

int changeCnt = 0;

bool IsOneDifferent(string a, string b)
{
    int cnt = 0;

    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == b[i])
        {
            cnt++;
        }
    }

    if (cnt != a.size() - 1)
    {
        return false;
    }

    return true;
}

void Dfs(string begin, string target, vector<string> words)
{
    while (begin != target)
    {
        if (IsOneDifferent(begin, target))
        {
            changeCnt++;
            break;
        }

        for (int i = 0; i < words.size(); i++)
        {
            if (IsOneDifferent(begin, words[i]))
            {
                begin = words[i];
                words.erase(words.begin() + i);
                changeCnt++;
                break;
            }
        }
    }
}

int solution(string begin, string target, vector<string> words) 
{
    int answer = 0;
    int cnt = 0;

    for (int i = 0; i < words.size(); i++)
    {
        if (words[i] == target)
        {
            cnt++;
            break;
        }
    }

    if (cnt == 0)
    {
        return 0;
    }

    Dfs(begin, target, words);
    answer = changeCnt;

    return answer;
}