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

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

문제 풀이

한 번에 한 개의 알파벳만 바꿀 수 있고 가능한 적은 단계를 거쳐야 하므로,

동적 계획법(dp)을 사용하여 각 단어에서 몇 번을 바꾸면 target이 되는지를 구하고 최소값을 반환하는 풀이를 사용했다.

 

이전에 방문했던 단어를 다시 방문하지 않도록 하는 visit 배열을 통해 무한루프에 빠지지 않도록 하고, 만약 현재 단어가 target 단어라면 0을 반환한다. 반환 값에 1을 더한 값과 이제까지 구한 최소 단계수를 비교하여 더 작은 수를 저장하고, 반복문이 끝나면 dp에 해당 값을 저장한다.

 

다만 모든 단어를 방문했을때 현재 단어와 한 개의 알파벳만 다른 단어를 마주치지 못하면 1000을 그대로 dp에 입력하여 해당 단어는 target이 될 수 없음을 나타냈다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
vector<int> dp;
int get_dp(string target, vector<int> visit, vector<string> words, int curr)
{
    if (dp[curr] != -1) return dp[curr];
    if (words[curr] == target)
    {
        dp[curr] = 0;
        return dp[curr];
    }

    int answer = 1000;

    for (int i = 0; i < words.size(); i++)
    {
        if (visit[i] == 1) continue;

        int same = 0;
        for (int j = 0; j < target.size(); j++)
        {
            if (words[curr][j] != words[i][j]) same++;
        }
        if (same == 1) {
            visit[i] = 1;
            answer = min(get_dp(target, visit, words, i) + 1, answer);
            visit[i] = 0;
        }
    }

    dp[curr] = answer;
    return answer;
}

int solution(string begin, string target, vector<string> words) {
    int answer = 1000;
    vector<int> dp_array(words.size(), -1);
    vector<int> visit(words.size(), -1);
    dp = dp_array;

    for (int i = 0; i < words.size(); i++)
    {
        int same = 0;
        for (int j = 0; j < target.size(); j++)
        {
            if (begin[j] != words[i][j]) same++;
        }
        if (same == 1)
        {
            visit[i] = 1;
            answer = min(get_dp(target, visit, words, i) + 1, answer);
            visit[i] = 0;
        }
    }

    if (answer == 1000) answer = 0;
    return answer;
}