#include <string>
#include <vector>
#include<algorithm>
#include<list>
using namespace std;
vector <vector<int>> adj;
vector <int> infos;
int maxSheep=0;
// 현재 노드, 양의 수 , 늑대의 수,남아있는 양 수, 방문여부 불린 벡터,현재 접근 가능한 노드 리스트
void dfs(int curr,int s,int w,int remainSheep,vector <bool> visited, list <int> canGo) {
maxSheep = max(s, maxSheep);
if (remainSheep == 0||s<=w) return;
for (auto i : adj[curr]) {
canGo.push_back(i);
}
for (list<int>::iterator next = canGo.begin(); next != canGo.end();++next) {
if (!visited[*next]){
if (infos[*next] == 0) {
visited[*next] = true;
canGo.erase(next);
dfs(*next, s + 1, w, remainSheep - 1,visited,canGo);
}
else if (infos[*next] == 1 && s > w + 1) {
visited[*next] = true;
canGo.erase(next);
dfs(*next, s, w + 1, remainSheep,visited, canGo);
}
}
}
return;
}
int solution(vector<int> info, vector<vector<int>> edges) {
int answer = 0;
int sheeps = 0;
adj.resize(info.size());
vector <bool> visited;
list <int> cango;
visited.resize(info.size(),false);
infos = info;
for (auto i:info)
{
if (i == 0)sheeps++;
}
for (auto i : edges) {
adj[i[0]].push_back(i[1]);
}
for (auto i : adj[0]) {
cango.push_back(i);
}
dfs(0,1,0,sheeps-1,visited,cango);
return maxSheep;
}
#include <string>
#include <vector>
#include<algorithm>
#include<list>
using namespace std;
vector <vector<int>> adj;
vector <int> infos;
int maxSheep=0;
// 현재 노드, 양의 수 , 늑대의 수,남아있는 양 수, 현재 접근 가능한 노드 리스트
void dfs(int curr,int s,int w,int remainSheep, list <int> canGo) {
if (infos[curr] == 1) {
w++;
if (s <= w)return;
}
else {
s++;
remainSheep--;
maxSheep = max(s, maxSheep);
// 트리에 양이 남아있지 않으면 그 이후 노드를 볼 필요가 없다.
if(remainSheep==0)return;
}
list <int> newCanGo(canGo);
for (auto i : adj[curr])
newCanGo.emplace_back(i);
newCanGo.remove(curr);
for (auto next : newCanGo)
dfs(next, s, w, remainSheep, newCanGo);
return;
}
int solution(vector<int> info, vector<vector<int>> edges) {
int answer = 0;
int sheeps = 0;
adj.resize(info.size());
list <int> cango;
infos = info;
for (auto i:info)
{
if (i == 0)sheeps++;
}
for (auto i : edges) {
adj[i[0]].push_back(i[1]);
}
dfs(0,0,0,sheeps,cango);
return maxSheep;
}
양방향 그래프
-> 불필요한 무한 재귀호출 가능성 有
삼차원 visited 배열 [현재 노드,양의수, 늑대의 수].
visit[A][B][C] = true : A번 노드에 양을 B마리 늑대를 C마리를 데리고 방문한 적이 있다는 뜻. 참고링크
->직접 해보진않았지만 우연히 겹치는 같은 양의수,늑대의 수 경우가 있으면 우짜지?
갈 수 있는 정점을 따로 담아서 재귀호출
->내가 푼 방법
dp로 n마리 모은 경로를 바탕으로 n+1 마리를 모을 수 있는 경우 구하기 반복 참고링크