[프로그래머스/C++] 불량 사용자(DFS)

푸는 방법은 크게 두가지 인 것 같다. 

 

1)DFS

2)비트마스크

 

나는 비트마스크를 몰라서 DFS로 풀었고 중복없이 담아주는 set container를 이용하여 조합을 만들었고, set container의 size를 return했다. set은 처음 써봤는데 유용하다!! 유사문제로 백준 1987번 알파벳문제가 있다.

 

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

bool visit[8]; //방문처리
set <set<string>> ansList; //답이 되는 조합을 담는 set -> 크기를 return하면 된다.

bool starcmp(string ban, string user){ 
    /*
    banned_id와 user_id가 일치하는지 판단
    */
    if(ban.size()!=user.size())return false;
    else{
        for(int i=0;i<ban.size();i++){
            if(ban[i]!='*'){
                if(ban[i]!=user[i])return false;
            }
        }
    }
    return true;
}

void dfs(vector<string>& user_id, vector<string>& banned_id, int nx, set<string> combi){
    /*
    중복되지 않는 아이디 조합 생성
    */
    
    //종료조건
    if(nx == banned_id.size()) {
        ansList.insert(combi);
        return;
    }
    
    for(int i=0;i<user_id.size();i++){
        if(visit[i] == 1 || !starcmp(banned_id[nx], user_id[i])) continue;
        
        set<string> ncombi = combi;
        ncombi.insert(user_id[i]);
        visit[i]=1;
        dfs(user_id, banned_id, nx+1, ncombi);
            
        //다시 돌려줘야 다른 경우의 수 만들 수 있음
        visit[i]=0;     
    }   
}

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