양과 늑대

노드가 17개이기 때문에 완전 탐색을 한다.

비트마스킹을 이용해서 방문한 노드들을 표현했다.

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

코딩테스트 연습 - 양과 늑대

 

참고 : 

https://blog.encrypted.gg/1029

https://wadekang.tistory.com/10

[c++][프로그래머스] 양과 늑대

#include <vector>

#include <queue>

#include <algorithm>

 

using namespace std;

 

struct Node {

    int sheep; // 모은 양의 수

    int wolf; // 모은 늑대의 수

    int route; // 현재까지 방문한 노드들

 

    Node(int _sheep, int _wolf, int _route) : sheep(_sheep), wolf(_wolf), route(_route) {}

};

 

bool visit[132000];

 

int solution(vector<int> info, vector<vector<int>> edges) {

    int S = info.size();

    vector<vector<int>> g(S);

    for(auto edge: edges) {

        g[edge[0]].push_back(edge[1]);

    }

 

    queue<Node*> q;

    

    q.push(new Node(1, 0, (1 << 0))); // 루트 노드

    visit[(1<<0)] = true;

    int answer = 1;

 

    while(!q.empty()) {

        Node *cur = q.front(); q.pop();

 

        int sheep = cur->sheep;

        int wolf = cur->wolf;

        int route = cur->route;

 

        for(int i=0; i<S; ++i) {

            if(route & (1 << i)) { // 현재까지 방문한 노드에서(두 비트가 같아야 1을 반환, 전체적으로 현재까지 방문한 노드이면 1을 반환한다)

                for(auto next: g[i]) { // 다음으로 이동할 노드

                   int next_route = route | (1 << next); //현재 루트에 다음 노드를 더한다.( | 연산자는 하나라도 1일때 1을 반환한다.)

                    if(info[next] == 0) { // 양

                        if(visit[next_route]) continue; // 만약 똑같이 방문한적이 있다면 pass

 

                        answer = max(answer, sheep+1);

                        visit[next_route] = true;

                        q.push(new Node(sheep+1, wolf, next_route));

                    }

                    else { // 늑대

                        if(sheep > wolf+1) {

                            if(visit[next_route]) continue;

 

                            visit[next_route] = true;

                            q.push(new Node(sheep, wolf+1, next_route));

                        }

                    }

                }

            }

        }

    }

 

    return answer;

}