[프로그래머스][level3] 양과 늑대 (C++)

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

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

 

 

[난이도] level3
[유형] 완전탐색

[풀이]
총 노드의 개수가 최대 17개밖에 되지 않기 때문에 방문할 수 있는 모든 경우의 수를 다해봐도 문제 해결이 가능합니다.

void sol(int n,set<int> s,int a,int b) 이라는 재귀함수를 만들어서 아래와 같이 정의하였습니다.
n : 현재 방문한 노드,
s : 다음에 방문할 수 있는 노드,
a : 현재 같이있는 양의 수,
b : 현재 같이있는 늑대의 수

현재 방문한 노드의 자식 노드들을 s에 추가해준 줍니다.
그러면 이제 s에 들어있는 노드들은 다음에 방문할 수 있는 모든 노드가 들어있게 됩니다.
s에 들어있는 노드들을 순차적으로 방문하는 재귀함수를 호출해주면서 a , b 값을 누적해가면
최댓값을 구할 수 있습니다.

 

#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int N,ans;
vector<int> adj[17],info;
void sol(int n,set<int> s,int a,int b){
    if(info[n]) b++;
    else a++;
    if(b>=a) return;
    s.erase(n);
    ans=max(a,ans);
    for(auto nxt : adj[n]) s.insert(nxt); 
    for(auto v : s) sol(v,s,a,b);
}
int solution(vector<int> _info, vector<vector<int>> edges) {
    N=info.size();
    info=_info;
    for(auto eg : edges) adj[eg[0]].push_back(eg[1]);
    sol(0,{0},0,0);
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/양과_늑대.cpp