[프로그래머스]2019 카카오 개발자 겨울 인턴십 : 불량 사용자 (level 3)(c++)

https://programmers.co.kr/learn/courses/30/lessons/64064?language=cpp

코딩테스트 연습 - 불량 사용자

 

dfs + 백트랙킹

#include <string>
#include <vector>
#include <set>

using namespace std;

set<int> com_set;

void dfs(vector<vector<int>> &cands, set<int> &pick_ban, int depth)
{
    // 종료조건 : depth가 제재 아이디목록 길이일 때
    if (depth == cands.size())
    {
        /*
            제재 아이디 조합set에 넣을 목록 만들기
            ( set특성상 오름차순으로 제재아이디 목록이 만들어짐 ex)1345 )
        */
        int pick_set = 0;
        for (auto iter = pick_ban.begin(); iter != pick_ban.end(); ++iter)
        {
            pick_set *= 10;
            pick_set += *iter;
        }

        /*
            제재 아이디 조합 set에 insert
            : 기존에 동일한 조합이 있었다면 무시될 것
        */
        com_set.insert(pick_set);
       
        return;
    }

    // depth번째의 제재아이디 후보숫자열 탐색
    for (int i = 0; i < cands[depth].size(); ++i)
    {
        /*
            pick_ban set에 추가 되지 않은 숫자라면 
            set에 추가 후, depth + 1로 재귀함수 호출
        */
        int user = cands[depth][i] + 1;
        if (pick_ban.find(user) == pick_ban.end())
        {
            pick_ban.insert(user);
            dfs(cands, pick_ban, depth + 1);
            pick_ban.erase(user); 
        }
    }
}

// 제재 아이디 후보인지 확인
bool check_if_cand(string &ban, string &user)
{
    // 길이가 다르면 제재 아이디X
    if (ban.size() != user.size())
    {
        return false;
    }

    /*
        제재 아이디와 유저 아이디의 같은자리 문자가 서로 다르면 (* 제외)
        : 제재 아이디X
    */
    for (int i = 0; i < ban.size(); ++i)
    {
        if (ban[i] != '*' && ban[i] != user[i])
        {
            return false;
        }
    }
    return true;
}

int solution(vector<string> user_id, vector<string> banned_id) {

    int ban_size = banned_id.size();
    int user_size = user_id.size();
    vector<vector<int>> cands(ban_size);

    for (int i = 0; i < ban_size; ++i)
    {
        for (int j = 0; j < user_size; ++j)
        {
            /*
                j번째 사용자 아이디가 i번째 제재 아이디가 될 수 있다면
                i번째 제재아이디 후보 숫자열에 j push
            */
            if (check_if_cand(banned_id[i], user_id[j]))
            {
                cands[i].push_back(j);
            }
        }
    }

    // 깊이우선 탐색과 백트랙킹으로 중복되지 않는 제재아이디 목록 만들기
    set<int> pick_ban;
    dfs(cands, pick_ban, 0);

    // 가능한 제재 아이디 목록개수 반환
    return com_set.size();
}

 

열심히 주석 설명을 달았는데, 이 코드는 어쩐지 주석을 달으니 더 복잡해보인다.

아래는 주석 없는 코드!

 

#include <string>
#include <vector>
#include <set>

using namespace std;

set<int> com_set;

void dfs(vector<vector<int>> &cands, set<int> &pick_ban, int depth)
{
    if (depth == cands.size())
    {
        int pick_set = 0;
        for (auto iter = pick_ban.begin(); iter != pick_ban.end(); ++iter)
        {
            pick_set *= 10;
            pick_set += *iter;
        }

        com_set.insert(pick_set);
       
        return;
    }


    for (int i = 0; i < cands[depth].size(); ++i)
    {
        int user = cands[depth][i] + 1;
        if (pick_ban.find(user) == pick_ban.end())
        {
            pick_ban.insert(user);
            dfs(cands, pick_ban, depth + 1);
            pick_ban.erase(user); 
        }
    }
}

bool check_if_cand(string &ban, string &user)
{
    if (ban.size() != user.size())
    {
        return false;
    }

    for (int i = 0; i < ban.size(); ++i)
    {
        if (ban[i] != '*' && ban[i] != user[i])
        {
            return false;
        }
    }
    return true;
}

int solution(vector<string> user_id, vector<string> banned_id) {

    int ban_size = banned_id.size();
    int user_size = user_id.size();
    vector<vector<int>> cands(ban_size);

    for (int i = 0; i < ban_size; ++i)
    {
        for (int j = 0; j < user_size; ++j)
        {
            if (check_if_cand(banned_id[i], user_id[j]))
            {
                cands[i].push_back(j);
            }
        }
    }

    set<int> pick_ban;
    dfs(cands, pick_ban, 0);

    return com_set.size();
}

 

 

위 문제를 푸는 순서는 다음과 같다.

1. 각 제재 아이디와 유저 아이디를 비교해서, 유저 아이디가 해당 제재 아이디의 후보가 될 수 있으면

유저 아이디의 인덱스 번호를 cands 2차원 배열에 넣는다. 

2. dfs + 백트랙킹으로 서로 중복되지 않는 제재 아이디 리스트를 만든다.

3. 2에서 만들어진 리스트를 <제재 아이디 리스트 set>에 넣어서 중복되지 않는 <리스트 set>을 만든다.

4. 리스트 set의 크기 반환!

 

 

백트랙킹의 개념을 모른다면 풀기 어려운 문제라고 생각한다.

작년 말에 알고리즘을 잘 몰랐을 때 시험삼아 인턴십 코테를 치렀었는데

정말 개발새발 코드를 짜다가 결국 제출을 못했던 기억이 난다ㅋ.ㅋ

 

 

백트랙킹(Backtracking) : 다시 돌아와서 추적하기

가능한 조합을 트리 형태로 그릴 때 한 나뭇가지 방향으로 쭉~ 그림을 그리고

다시 돌아와서 두번째 나뭇가지 방향으로 쭉~ 그림을 그리는 것을 코드로 구현한 것이다. 

아래의 틀이 전형적인 dfs + 백트랙킹 구조이다. 

void dfs(vector<vector<int>> &cands, set<int> &pick_ban, int depth)
{
    if (depth == cands.size())
    {
       	...
        return;
    }

    for (int i = 0; i < cands[depth].size(); ++i)
    {
        int user = cands[depth][i] + 1;
        if (pick_ban.find(user) == pick_ban.end())
        {
            pick_ban.insert(user);
            dfs(cands, pick_ban, depth + 1);
            pick_ban.erase(user); //<-------------- 백트랙킹을 위한 후처리
        }
        
	/*
		cands[depth][0]를 pick_ban에 넣고나서 
		재귀함수가 제 할일을 마치고 돌아오면
		다시 원상복귀를 해주고 이제 cands[depth][1] 차례!
	*/
    }
}

 

 

 

백트랙킹을 공부할 때 참고했던 블로그

[알고리즘] 백트래킹(Backtracking)이란? (feat. DFS, 기준함수, sum of subset)