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

프로그래머스 양과 늑대 [2022 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/92343

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

문제 풀이

• 이 문제는 BFS, 비트마스킹을 사용해 해결했습니다.
• 루트 노드에서 시작하여 다음으로 방문할 수 있는 모든 경우의 수를 추가하며 모은 양의 수가 최대가 되는 경우를 찾습니다. 
• 노드의 개수가 최대 17개로 제한되어 있기 때문에 모든 경우의 수를 따져도 2^17 = 131072개 입니다. visit 배열을 하나 선언하여 노드들을 똑같이 방문했던 적이 있다면 패스합니다. 

위의 예제에서 아래와 같은 과정으로 그래프를 탐색하며 정답을 도출합니다. 

 

루트 노드를 시작으로 다음으로 갈 수 있는 노드 탐색

1번 노드를 가게 되면 양이 잡아 먹히기 때문에 2번 노드만 방문합니다.

 

현재 [0, 2]번 노드 방문, 다음으로 갈 수 있는 노드 탐색

현재 [0, 2]번 노드를 방문한 상태에서 다음으로 탐색할 수 있는 노드는 0번에서 1번, 2번에서 5번, 2번에서 6번, 총 3가지 노드가 있습니다. 위와 같이 현재 방문한 노드들에서 다음으로 방문 할 수 있는 노드들을 추가하며 그래프를 탐색하고 모은 양의 수가 최대가 되는 경우를 찾게 됩니다. 

코드

#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)) { // 현재까지 방문한 노드에서
                for(auto next: g[i]) { // 다음으로 이동할 노드
               	    int next_route = route | (1 << next);
                    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;
}

실행 결과