2022 KAKAO BLIND RECRUITMENT / 양과 늑대

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

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> info;
map<int, vector<int>> tree;
int ans;

void dfs(int cur, int sheep, int wolf, vector<int> cand) {
    sheep += info[cur] ^ 1;
    wolf += info[cur];

    if (sheep <= wolf) return;
    ans = max(ans, sheep);

    for (auto t : tree[cur])
        cand.push_back(t);

    for (auto e : cand) {
        vector<int> next;
        for (auto t : cand) {
            if (t == e) continue;
            next.push_back(t);
        }

        dfs(e, sheep, wolf, next);
    }
}

int solution(vector<int> in, vector<vector<int>> edges) {
    info = in;
    for (int i = 0; i < edges.size(); ++i) {
        tree[edges[i][0]].push_back(edges[i][1]);
    }

    dfs(0, 0, 0, {});

    return ans;
}

완전 탐색. 중복 상태가 많아서 비효율적이다.

중복 체크 적용.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> info;
map<int, vector<int>> tree;
int ans;

int visit[1 << 17];

void dfs(int state) {
    if (visit[state]) return;
    visit[state] = true;

    int n = info.size();
    int sheep = 0, wolf = 0;
    for (int i = 0; i < n; ++i) {
        if ((state & (1 << i)) == 0) continue;
        sheep += info[i] ^ 1;
        wolf += info[i];
    }

    if (sheep <= wolf) return;
    ans = max(ans, sheep);

    for (int i = 0; i < n; ++i) {
        if ((state & (1 << i)) == 0) continue;
        for (auto t : tree[i]) dfs(state | (1 << t));
    }
}

int solution(vector<int> in, vector<vector<int>> edges) {
    info = in;
    for (int i = 0; i < edges.size(); ++i) {
        tree[edges[i][0]].push_back(edges[i][1]);
    }

    dfs(1);

    return ans;
}