WILDCARD (중, p. 218)

처음에 이 문제를 왜 DP로 풀어야 하는지 잘 몰랐음.

일단 무식하게 다 탐색해도 돌아갈 거라 생각하고, DFS로 완탐하도록 코드를 짜고 있었는데,

dfs()에서 현재 wildcard에서 바라보는 문자를 wildcard[wi]라 하고, 문자열 s에서 바라보는 문자를 s[si]라고 하면, 상태공간 dp[wi][si]는 항상 값이 똑같다는 것을 catch하게 됨.

즉, dp[wi][si]는 wildcard.substr(wi)가 s.substr(si)를 봤을 때 일치하는지 여부를 나타내고, 이 상태는 유일한 답을 가짐. 그래서 DP로 문제를 풀 수 있었음.

#include <bits/stdc++.h>
using namespace std;
string wildcard, str[51];
vector<string> ans_list;
int lim;
bool chk[101][101];
bool dp[101][101];
void Init() {
    memset(chk,false,sizeof(chk));
}
bool dfs(int wi, const string & s, int si, int lim) {
    if(wi==wildcard.size() && si==s.size()) {
        return dp[wi][si] = true;
    }

    if(wi==wildcard.size() && si<s.size()) return false;
    if(s.size()-si<lim) return false;

    if(chk[wi][si]) return dp[wi][si];

    chk[wi][si] = true;
    bool & ret = dp[wi][si];

    ret = false;
    if(wildcard[wi] == '*') {
        //wildcard를 소모하는 경우
        ret |= dfs(wi+1,s,si,lim);
        if(ret) return true;

        //wildcard를 소모하지 않는 경우
        for(int i = si + 1; i <= s.size(); i++) {
            ret |= dfs(wi, s, i, lim);
            if(ret) return true;
        }
    }
    else if(wildcard[wi] == '?') {
        ret |= dfs(wi+1,s,si+1,lim-1);
    }
    else {
        if(wildcard[wi] == s[si]) {
            ret |= dfs(wi+1,s,si+1,lim-1);
        }
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        cin >> wildcard;
        int n; cin >> n;
        for(int i=0; i<n; i++) {
            cin >> str[i];
        }

        int cnt=0;
        for(int i=0; i<wildcard.size(); i++) {
            if(wildcard[i] == '*') cnt++;
        }
        lim = wildcard.size()-cnt;

        ans_list.clear();
        for(int i=0; i<n; i++) {
            Init();
            if(dfs(0,str[i],0,lim)) {
                ans_list.emplace_back(str[i]);
            }
        }

        sort(ans_list.begin(), ans_list.end());
        for(int i=0; i<ans_list.size(); i++) {
            printf("%s\n", ans_list[i].c_str());
        }
    }
    return 0;
}