231228 양과 늑대

List<List<Integer>> graph = new ArrayList<>();

public int dfs(int sheep, int wolf, int curNode, List<Integer> nextNodes, int[] info) {
	if (info[curNode] == 0)
		sheep++;
	else
		wolf++;

	int ans = sheep;
	if (sheep <= wolf)
		return ans;

	for (int i = 0; i < nextNodes.size(); i++) {
		int nextNode = nextNodes.get(i);
		List<Integer> stackNodes = new ArrayList<>(nextNodes);
		stackNodes.remove((Integer) nextNode);
		stackNodes.addAll(graph.get(nextNode));
		ans = Math.max(ans, dfs(sheep, wolf, nextNode, stackNodes, info));
	}

	return ans;
}

public int solution(int[] info, int[][] edges) {
	int nodeLength = info.length;
	for (int i = 0; i < nodeLength; i++) {
		graph.add(new ArrayList<>());
	}

	int edgeLength = edges.length;
	for (int i = 0; i < edgeLength; i++) {
		graph.get(edges[i][0]).add(edges[i][1]);
	}

	List<Integer> nextNodes = new ArrayList<>(graph.get(0));
	return dfs(0, 0, 0, nextNodes, info);
}

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