[프로그래머스] 단어 퍼즐

단어 퍼즐

문제) https://programmers.co.kr/learn/courses/30/lessons/12983

풀이)

처음에 BFS를 이용해서 풀었으나 효율성을 통과하지 못했다.

효율성 통과 x 코드)

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
bool cmp(const string &a, const string &b) {
    return a.length() > b.length();
}
 
int solution(vector<string> strs, string t)
{
    int answer = 0;
    sort(strs.begin(), strs.end(), cmp);
    queue <string> qu;
    vector <bool> check(t.length(), false);
    int cnt = 0;
    qu.push("");
    while (!qu.empty()) {
        int size = qu.size();
        while (size--)
        {
            string compare = qu.front();
            qu.pop();
            if (compare == t) return cnt;
 
            for (int i = 0; i < strs.size(); i++) {
                string next = compare + strs[i];
                if (check[next.length()])continue;
                if (next.length() <= t.length() && t.substr(0, next.length()) == next) {
                    check[next.length()] = true;
                    qu.push(next);
                }
            }
 
        }
 
        cnt++;
    }
 
    return -1;
}

그래서 다른 분의 글을 참고해서 재귀적 dp로 풀었다.(최단 비용 도로 개수 구하는 방법처럼)

효율성 통과 o 코드)

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321
 
vector <int> dp;
bool cmp(const string &a, const string &b) {
    return a.length() > b.length();
}
int dfs(vector <string> &strs, string &t, int len) {
    if (len == t.length()) return 0;
    if (dp[len] != -1) return dp[len]; //이전에 계산한 값이 존재
 
    dp[len] = INF;
    for (int i = 0; i < strs.size(); i++) {
        if (strs[i].length() + len <= t.length()) {
            bool flag = true;
            for(int j = 0; j < strs[i].size(); j++) {
                if(t[len + j] != strs[i][j]) {
                    flag = false;
                    break;
                }
            }
            if(flag) {  
                dp[len] = min(dp[len], dfs(strs, t, strs[i].length() + len) + 1);
            }
        }
 
    }
    return dp[len];
}
 
int solution(vector<string> strs, string t)
{
    int answer = 0;
    sort(strs.begin(), strs.end(), cmp);
 
    dp.assign(t.length(), -1);
 
    return dfs(strs, t, 0) == INF ? -1 : dp[0];
}