[ALGORITHM] LEVEL3 2022 KAKAO BLIND RECRUITMENT - 양과 늑대

https://school.programmers.co.kr/learn/courses/30/lessons/92343#

프로그래머스

주의할 점

• 어째서 인지는 모르겠으나 중복체크를 하지않은 단순 완전탐색으로도 풀리는 것 같습니다.
• 최악의 경우 피보나치 이상의 시간복잡도가 걸리게 됩니다. (한 가지를 선택하면 2개씩 늘어남 + 중복에 대한 순서 가지수)
• 최대 17개 이므로 단순 방문체크가 아닌 비트마스킹을 사용하여야 최악의 경우를 해결할 수 있습니다.

예제

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14], [7, 15], [7, 16]]
17

코드

#include <string>
#include <vector>

using namespace std;

int answer = 1;
vector<int> way[17];
bool vst[1<<17];
int N;

void dfs(vector<int>& info, int sheep, int wolf, int chk){
    answer = max(sheep,answer);
    
    for(int i=0;i<N;++i){
        if(1 & chk>>i){
            for(int j=0,sz=way[i].size();j<sz;++j){
                int next=way[i][j];
                int nchk = (chk | 1<<next);
                int nsheep = sheep + (info[next]==0);
                int nwolf  = wolf + (info[next]==1);

                if(nsheep <= nwolf || (vst[nchk]))
                    continue;

                vst[nchk]=true;
                dfs(info, nsheep, nwolf, nchk);
            }
        }
        
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    N=info.size();
    for(int i=0,sz=edges.size();i<sz;++i){
        way[edges[i][0]].push_back(edges[i][1]);
    }
    vst[1]=true;
    dfs(info,1,0,1);
    
    return answer;
}

참고

https://blog.encrypted.gg/1029

[2022 KAKAO Blind Recruitment] Q5. 양과 늑대 (C++, Python, Java)