[C++로 풀이] 불량 사용자 (DFS)⭐⭐⭐

📌 불량 사용자

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

void DFS(vector<string>& user_id, vector<string>& banned_id, set<string>& selected_list, vector<string> temp, map<string, bool> visited, int index)
{
    if (index == banned_id.size()) {
        string s = "";
        sort(temp.begin(), temp.end());
        for (int i = 0; i < temp.size(); i++)
            s += temp[i];
        selected_list.insert(s);
        return;
    }

    for (int i = 0; i < user_id.size(); i++) {
        if (visited[user_id[i]] == true)
            continue;
        if (banned_id[index].length() != user_id[i].length())
            continue;
        bool flag = true;
        for (int j = 0; j < user_id[i].length(); j++) {
            if (banned_id[index][j] != user_id[i][j]) {
                if (banned_id[index][j] == '*')
                    continue;
                else {
                    flag = false;
                    break;
                }
            }
        }
        if (flag) {
            temp[index] = user_id[i];
            visited[user_id[i]] = true;
            DFS(user_id, banned_id, selected_list, temp, visited, index + 1);
            visited[user_id[i]] = false;
            // 잘못되서 돌아오는 경우에도 빠꾸할 수 있어야해. 다음 for문에서 채택될 수 있게! (이거 안해주면 다음 for문에 true인 상태로 넘겨지는 것이다.)
        }
        }
    }

    return;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;

    set<string> selected_list;
    vector<string> temp(banned_id.size());
    map<string, bool> visited;
    DFS(user_id, banned_id, selected_list, temp, visited, 0);
    
    answer = selected_list.size();

    return answer;
}

아이디가 최대 8 개 밖에 안되기 때문에 각각의 banned_id 원소에 대응될 수 있는 아이디들의 조합을 모~두 구하되 기존에 이미 구해진적이 있는, 중복인 것은 걸러주는걸로 코드를 짰다.

• DFS (index 👉 이번에 대응하는 아이디들 검사할 banned_id원소의 인덱스. DFS의 깊이 depth와도 같음)
  • 매 DFS 단계마다 (= 현재의 banned_id 원소마다) user_id 에서 해당 banned_id 원소에 대응 될 수 있는 아이디를 해당 조합에 추가한다.
  • 하나의 banned_id[index] 자리엔 여러 아이디가 대응될 수 있다. 그래서 DFS 단계(banned_id 원소)마다 첫번째 for문에서 유저 아이디를 전부 순회하는 이유다.
    • 1️⃣ banned_id[index]에 대응될 수 있는 user_id 원소를 찾아야 한다. 길이도 같고 *을 제외하고는 다 같은 문자라면 대응될 수 있는 아이디다.
      • 단, 해당 아이디는 현재의 DFS 단계까지 만들어온 “현재의 조합”에 이미 포함되어 있다면 안된다. (visited[user_id[i]] 가 false여야 함)
    • 2️⃣ 찾았다면
      • temp 문자열에 이 아이디를 붙인다. 왜 그런지는 종료 조건에서 설명.
      • 조합에 넣기로 결정된 이 user_id[i]가 현재의 DFS 조합에서 다시 등장하지 못하도록 방문 체크
      • DFS 를 재귀적으로 진행한다. banned_id[index + 1]에 대응하는 아이디를 조합에 포함시키러 출발
      • DFS 끝나고 돌아오면 user_id[i]를 방문 "해제"해주어야 한다.
        • 만약 해당 조합이 완성되는데에 실패해서 다시 돌아와야될 수도 있는데 이렇게 방문 해제를 해주지 조합이 만들어지는데 실패한 아이디라도 다음에 포함되지 못하게 된다. 방문 체크가 되있는 채로 다음 for문으로 넘거가기 때문이다. 매 재귀 단계마다 모든 user_id를 검사하니 다시 포함될 수 있도록 해야 한다. 그리고 만약 해당 조합이 완성되는데 성공했다 하더라도 해당 조합은 끝난 것이므로 다음 for문의 다른 user_id 원소가 채택되는 것에서 시작하는 DFS에서도 다시 등장할 수도 있어야 함.
  • 종료 조건 👉 모든 banned_id에 대응하는 아이디 조합 하나를 완성함
    • temp를 정렬 시킨다. 순서를 없애기 위해서!
      • 원소 문자열들이 합체되서 만들어진 temp를 “정렬”시켜서(순서 통일) 이걸 set 에 보관하여 중복을 거를 것이다. 나중에 완성된 temp를 정렬(중복 판별에 순서가 의미 없도록)시킨 값이 set 컨테이너 selected_list에 이미 있다면 set의 특성상 자연스럽게 걸러진다.

두번째 예시 banned_id = [“rodo”, “rodo”, “******”] 을 예로 DFS 과정을 설명해보자면

• *rodo (banned_id[0])
  • “frodo” 일치 👉 현재의 조합 [“frodo”]
    • *rodo (banned_id[1])
      • “frodo” 일치 But ❌ 현재의 조합에 포함되어 방문 체크 되어 있으니 불가
      • “crodo” 일치 👉 현재의 조합 [“frodo”, “crodo”]
        • ****** (banned_id[2])
          • “abc123” 일치 👉 현재의 조합 [“frodo”, “crodo”, “abc123”]
            • ✔ 완성! selected_list에 “123abccddfoooorr”가 추가됨
          • “frodoc” 일치 👉 현재의 조합 [“frodo”, “crodo”, “frodoc”]
            • ✔ 완성! selected_list에 “ccdddffoooooorrr”가 추가됨
  • “crodo” 일치 👉 현재의 조합 [“crodo”]
    • *rodo (banned_id[1])
      • “frodo” 일치 현재의 조합 [“crodo”, “frodo”]
        • ****** (banned_id[2])
          • “abc123” 일치 👉 현재의 조합 [“crodo”, “frodo”, “abc123”]
            • ✔ 완성! selected_list에 “123abccddfoooorr”가 이미 있으므로 무시함
          • “frodoc” 일치 👉 현재의 조합 [“crodo”, “frodo”, “frodoc”]
            • ✔ 완성! selected_list에 “ccdddffoooooorrr”가 이미 있으므로 무시함
      • “crodo” 일치 But ❌ 현재의 조합에 포함되어 방문 체크 되어 있으니 불가

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기