양과 늑대

프로그래머스 양과 늑대 풀이

문제설명

진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

제한사항

• 2≤노드의 수≤17

노드의 수가 적고 트리구조라 완전탐색을 해도 가능한 시간이다. $2^{17} < 8^{6} < 10^6$ 이므로 10초안에 무조건 가능하다. 그렇기에 구현에만 초점에 맞추면 된다.

해결과정

현재까지의 양의 수와 늑대의 수를 기록하며 앞으로 이동할 수 있는 노드를 기록한다. 프로그래머스의 첫번째 예시 사진으로 설명하면, 0번을 방문했을 때 현재 양의 수는 1이고 늑대 수는 0이다. 또, 앞으로 갈 수 있는 방문지는 {1,8}이다. 이제, 실제 방문할 행선지를 구한다. 8은 불가능하고, 1은 가능하다. 1로 이동한뒤 같은 방식으로 값을 수하면, 양:2, 늑대:0, 앞으로 이동가능한 방문지는{2,4,8}이다. 이런식으로 구하면 모든 경우의 수를 확인할 수 있다.

소스코드

#include <bits/stdc++.h>
using namespace std;
vector<int> eds[18];
int node_size;
int ans = 0;

struct move{
    int sheep; // 양의 수
    int attack; // 늑대의 수
    int idx;
    vector<int> list; // 앞으로 갈 수 있는 노드들
};
struct compare{ //b가 되는 방향이 최소힙 or 최대힙을 고름 // b가 되는 쪽이 큰 값이면 최대힙
    bool operator()(const struct move& a, const struct move& b){
        return (a.sheep - a.attack) < (b.sheep - b.attack);
    }
};
int solution(vector<int> info, vector<vector<int>> edges) {
    node_size = info.size();
    for(vector<int>& edge : edges){
        eds[edge[0]].push_back(edge[1]);
    }
    priority_queue<struct move, vector<struct move>, compare> pq; // 양 - 늑대의 수
    pq.push({1,0,0,{eds[0]}});
    
    while(!pq.empty()){
        struct move cur= pq.top();
        //cout << cur.sheep << ' ' << cur.attack << '\n';
        // for(int i : cur.list)
        //     cout << i << ' ';
        // cout << '\n';
        pq.pop();
        ans = max(ans, cur.sheep);
        for(const int& i : cur.list){
            if(info[i] && cur.sheep <= cur.attack + 1) continue;
            
            vector<int> tmp;
            for(const int& j: cur.list){
                if(i == j) continue;
                tmp.push_back(j);
            }
            for(const int& j: eds[i]){
                tmp.push_back(j);
            }
            if(info[i]) pq.push({cur.sheep,cur.attack + 1,i,tmp});
            else pq.push({cur.sheep + 1,cur.attack,i,tmp});
        }
        
        
    }
    
    

    return ans;
    
}

배운점

처음에 중복된 연산(노드의 방문)을 줄이려고 우선순위큐를 썼으나, dp[x] = x 노드를 방문했을 때, 양의 수의 최댓값 으로 연산을 줄이는 것은 위험하다. (x 노드를 방문했을 때, dp[x]보다 양의수가 적다해서 문제가 정답이라고 보장할 수 없다.)

다른 사람들의 코드를 보니, 나처럼 vector 형식으로 리스트를 관리하는 것이 아닌 비트마스킹으로 리스트를 관리하는 것 같다.