programmers DFS/BFS | 불량 사용자

깊이 우선 탐색 문제
코딩테스트 연습 - 불량 사용자 | 프로그래머스

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

using namespace std;

vector<int> bit;

bool ft_can_match(string user, string ban) {
    if (user.length() != ban.length())
        return (false);
    for (int i = 0; i < user.length(); i++) {
        if (ban[i] == '*') {
            continue;
        }
        else if (user[i] != ban[i]) {
            return (false);
        }
    }
    return (true);
}

//https://dpdpwl.tistory.com/39
int dfs(vector<string> user_id, vector<string> banned_id, int bit_flag, int deep) {
    if (deep == banned_id.size()) {
        bit.push_back(bit_flag);
        return (0);
    }
    for (int i = 0; i < user_id.size(); i++) {
        if (!(bit_flag & (1 << i)) && ft_can_match(user_id[i], banned_id[deep]) == true) {
            int temp = dfs(user_id, banned_id, bit_flag + (1 << i), deep + 1);
        }
    }
    return (0);
}

// 제한사항이 많을 수 밖에 없음. 애초에 말이 안되는, 문제를 위한 문제기 때문
// 특히 응모한 사용자 아이디가 중복되지 않는다거나
// 불량사용자의 아이디는, 응모자 아이디 중 하나에 해당한다와 같은
// 갖가지의 전제가 붙을 수 밖에 없음

// banned_id size 만큼 재귀를 일으키면서, 다 돌게되면 카운팅.
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    dfs(user_id, banned_id, 0, 0);

    std::vector<int>::iterator it;

    sort(bit.begin(), bit.end());
    it = unique(bit.begin(), bit.end());
    bit.erase(it, bit.end());
    answer = bit.size();

    bit.erase(bit.begin(), bit.end());

    return answer;
}

int main() {
    int answer;

    //string vector initialization
    //https://www.delftstack.com/ko/howto/cpp/how-to-initialize-a-vector-in-cpp/
    vector<string> user_id = {"frodo", "fradi", "crodo", "abc123", "frodoc"};

    vector<string> banned_id1 = {"fr*d*", "abc1**"};
    answer = solution(user_id, banned_id1);
    cout << "ex1: " << answer << endl;

    vector<string> banned_id2 = {"*rodo", "*rodo", "******"};
    answer = solution(user_id, banned_id2);
    cout << "ex2: " << answer << endl;

    vector<string> banned_id3 = {"fr*d*", "*rodo", "******", "******"};
    answer = solution(user_id, banned_id3);
    cout << "ex3: " << answer << endl;
}

• 처음에는 경우의 수를 구하기 위해 애를 먹음
• 하지만 ****** 와 같은 banned id가 넘어온다면, 분기가 굉장히 복잡해짐
  • 거기다, 재귀 깊이에서는 그 분기를 처리하기 쉽지않음
• 그래서, 모든 재귀를 다 돌면서, 중복을 제거하는 식으로 만들려고 함
• user_id는 8개까지만 들어올 수 있다길래... int 형 변수 bit_flag를 하나 주고, bit 연산으로 데이터를 저장하는 식으로 풀이
• 다른 사람 풀이를 보니 set을 이용해서, 중복제거.
• dfs인데 단지 순열의 반복제거를 하는 문제로 둔갑...