Computer Science & Engineering

programmers.co.kr/learn/courses/30/lessons/64064#

처음 문제를 잘 이해하지 못하여 접근방법을 잘못 알았고 아래에 첨부한 풀이도 비효율적이지만 오랜 시간을 들여 풀었기 때문에 그대로 첨부하였다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int answer;
bool visit[9];
set<string> rst;
void dfs(int n, vector<string> &user_id, vector<string> &banned_id, string s) {
    if(n == banned_id.size()) {
        sort(s.begin(), s.end());
        rst.insert(s);
        return;
    }
    string now = banned_id[n];
    for(int i = 0; i < user_id.size(); i++) {
        if(visit[i] || now.size() != user_id[i].size()) continue;
        int chk = 0;
        for(int j = 0; j < now.size(); j++) {
            if(now[j] == '*') continue;
            if(user_id[i][j] != now[j]) {
                chk = 1;
                break;
            }
        }
        if(!chk) {
            visit[i] = 1;
            dfs(n+1, user_id, banned_id, s + to_string(i));
            visit[i] = 0;
        }
    }
    return;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    dfs(0, user_id, banned_id, "");
    answer = rst.size();
    return answer;
}

처음에는 그래프를 그려 2-sat으로 이분매칭을 이용하여 풀려고 했으나 뜻대로 되지 않아 백트래킹을 이용하여 풀었다. 

ban사용자를 하나씩 선택하여 방문하지 않은 user중 일치하는 것이 있는지 확인한 후 재귀적으로 반복한다. dfs함수의 맨 마지막 인자인 string은 지금까지 일치된 사용자의 인덱스 번호이다. 사용자를 모두 찾은 경우 string s를 정렬하여 set에 집어 넣는다. 이 과정은 중복이 일어나지 않게 하기 위해서이다. 모든 과정을 끝낸 후 set의 사이즈를 리턴하면 된다.