[DFS] 불량 사용자 - 2019 카카오 개발자 겨울 인턴십

경우의 수를 구하는 유형의 문제는 DFS 또는 DP 문제일 확률이 높다.

경우의 수를 조합이나 순열같은 수식으로 해결해보려고 시도해보았지만 꽤 복잡해서 DFS로 풀기로 결정했다.

 

해결 방법

먼저, banned_id의 1번째 id와 매칭 가능한 user_id가 있는지 확인해서 매칭 가능한 user_id를 발견했다면 save 벡터에 해당 user_id를 저장해둔다.

그리고 이후의 banned_id들에 대해서도 동일한 과정을 반복하여 모든 banned_id가 매칭되었다면 하나의 경우가 완성된 것이다. 이 때의 save 정보를 다른 벡터에 저장해놓고 DFS를 이어서 수행해주면 된다.

조건에 맞는 모든 경우들을 모두 저장했다면 중복되는 아이디 목록을 최종적으로 제거해주고 남은 경우의 수를 구하면 문제가 해결된다.

 

 

소스 코드

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

vector<string> ui; // user_id 저장
vector<string> bi; // banned_id 저장
vector<string> results; // 가능한 모든 경우 저장

bool visited[9];
string result;

// 불량 사용자일 경우가 있는지 확인
bool check(string bid, string uid){
    if(bid.length()!=uid.length()) return false;
    for(int i=0;i<bid.length();i++){
        if(bid[i]=='*') continue;
        if(bid[i]!=uid[i]) return false;
    }
    return true;
}

void dfs(vector<int> save) {
    // dfs 종료 조건 만족
    if(save.size()==bi.size()){
        result="";
        sort(save.begin(), save.end()); // 아이디 목록 정렬
        for(int i=0;i<save.size();i++) result+=to_string(save[i]); // 벡터를 문자열로 변환 - 예) {0, 2, 4} -> "024"
        results.push_back(result); // 현재 결과를 저장
        return;
    }
    // dfs 수행
    for(int i=0;i<ui.size();i++){
        if(!visited[i]&&check(bi[save.size()], ui[i])){
            visited[i]=true;
            save.push_back(i);
            dfs(save);
            visited[i]=false;
            save.pop_back();
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    vector<int> save; // 불량 사용자일 수도 있는 사용자(user_id의 index)를 담은 벡터
    
    // 전역 벡터 ui, bi에 복사
    ui.resize((int)(user_id.size()));
    copy(user_id.begin(), user_id.end(), ui.begin());
    bi.resize((int)(banned_id.size()));
    copy(banned_id.begin(), banned_id.end(), bi.begin());
    
    dfs(save); // 빈 save 벡터를 넣어서 dfs 수행
    
    // 중복된 아이디 목록을 제거
    sort(results.begin(), results.end());
    results.erase(unique(results.begin(),results.end()),results.end());
    return results.size();
}

 

테스트케이스 11개 모두 통과