[BOJ] 불량 사용자

[BOJ] 불량 사용자

Problem URL : 불량 사용자

첫 풀이

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

using namespace std;
bool dp[8][(1 << 8) + 1];
int answer;
int n, m;
vector<string> u;
vector<string> b;
void bfs(int ban_num, int visited) {
    dp[ban_num][visited] = true;
    if(ban_num == m) {
        answer++;
        return;
    }
    for(int i = 0; i < n; i++) {
        if(visited & (1 << i) || dp[ban_num + 1][visited | (1 << i)]) {
            continue;
        }
        if(u[i].length() != b[ban_num].length()) {
            continue;
        }
        bool match = true;
        int idx = u[i].length();
        while(--idx >= 0){
            if(b[ban_num][idx] != '*' && u[i][idx] != b[ban_num][idx]) {
                match = false;
                break;
            }
        }
        if(match) {
            bfs(ban_num + 1, visited | (1 << i));
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    answer = 0;
    u = user_id;
    b = banned_id;
    n = user_id.size();
    m = banned_id.size();
    bfs(0,0);
    return answer;
}

좀더 간단하게 풀은 풀이

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;
bool visit[(1 << 8) + 1];
int answer;
int n, m;
vector<string> u;
vector<string> b;
set<int> s;
void bfs(int ban_num, int visited) {
    if(ban_num == m) {
        s.emplace(visited);
        return;
    }
    for(int i = 0; i < n; i++) {
        if(visited & (1 << i)) {
            continue;
        }
        if(u[i].length() != b[ban_num].length()) {
            continue;
        }
        bool match = true;
        int idx = u[i].length();
        while(--idx >= 0){
            if(b[ban_num][idx] != '*' && u[i][idx] != b[ban_num][idx]) {
                match = false;
                break;
            }
        }
        if(match) {
            visit[visited | (1 << i)] = true;
            bfs(ban_num + 1, visited | (1 << i));
            visit[visited | (1 << i)] = false;
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    u = user_id;
    b = banned_id;
    n = user_id.size();
    m = banned_id.size();
    bfs(0,0);
    return s.size();
}