프로그래머스 - 단어 변환 - C++

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int minA = 2100000000;
string be;
string tar;
int check[51];

bool isChange(string word, string s)
{
    int c = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if (word[i] == s[i])c++;
    }
    return (c + 1 == s.length()) ? true : false;
}

void D(vector<string> words, int cnt, int n, string cur)
{
    if (cur == tar)
    {
        if (cnt < minA)minA = cnt;
        return;
    }
    if (n == words.size())
    {
        if (cur == tar && cnt < minA)minA = cnt;
        return;
    }
    for (int i = 0; i < words.size(); i++)
    {
        if (check[i] == 0 && isChange(words[i], cur))
        {
            check[i] = 1;

            D(words, cnt+1, n + 1,words[i]);

            check[i] = 0;
        }
    }
}

int solution(string begin, string target, vector<string> words) {
    int answer = 0;
    be = begin;
    tar = target;
    D(words, 0, 0, begin);
    if (minA == 2100000000)return 0;
    return minA;
}

설명

DFS, 재귀함수

만약 words 중 한 개의 단어로 변환시키면 이후 벌어질 수 있는 모든 경우의 수를 따져서 target을 만드는 최소변환 횟수를 찾는 문제이기 때문에 DFS를 이용하였다. 

 

먼저 isChange() 함수는 string 타입인 word 와 s 를 비교해 1개의 알파벳만 다른지 체크해주는 함수이다. 

 

DFS를 실행하는 함수 D의 로직은 이렇다.

 

1. target을 만들었거나 한번씩 모든 단어를 사용했다면 재귀함수를 종료한다. 

2. words에 있는 모든 단어를 전부 검사하며 바꿀 수 있는지 검사한다. 

3. 바꿀 수 있다면 재귀적으로 함수를 호출해 변환횟수와 바뀐 단어를 매개변수로 넘긴다. 

 

이렇게 재귀함수가 종료되면 전역변수인 cnt에 최소값이 들어있게 되며 출력한다.