[프로그래머스] 양과 늑대 (JAVA)

문제 설명

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

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.

제한사항

2 ≤ info의 길이 ≤ 17
info의 원소는 0 또는 1 입니다.
info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
0은 양, 1은 늑대를 의미합니다.
info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
edges의 세로(행) 길이 = info의 길이 - 1
edges의 가로(열) 길이 = 2
edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
0번 노드는 항상 루트 노드입니다.

Code

import java.util.*;
class Solution {
    private static int MaxCnt;
	private static Map<Integer, List<Integer>> nodes;
    public int solution(int[] info, int[][] edges) {
        MaxCnt = 0;
		nodes = new HashMap<>();
		for(int[] e : edges) {
			if(!nodes.containsKey(e[0])) nodes.put(e[0], new ArrayList<>());
			nodes.get(e[0]).add(e[1]);
		}
		List<Integer> list = new ArrayList<>();
		list.add(0);
		dfs(0, 0, 0, list, info);
		return MaxCnt;
    }
    public void dfs(int idx, int s, int w, List<Integer> list, int[] info) {
		if(info[idx]==0) s+=1;
		else w+=1;
		if(s<=w) return;
		
		MaxCnt = Math.max(MaxCnt, s);
		
		List<Integer> next = new ArrayList<>();
		next.addAll(list);
		if(nodes.containsKey(idx)) next.addAll(nodes.get(idx));
		next.remove(Integer.valueOf(idx));
		
		for(int n : next) {
			dfs(n, s, w, next, info);
		}
		
		return;
	}
}

Comment

왼쪽 오른쪽 왔다리 갔다리 해야하는 트리라 계속해서 다음 노드를 갖고 있으면서 DFS로 풀었다.
애를 먹었던 부분은 dfs부분에서 List 새로 할당하여 다음 노드로 보내는 부분만 사용하고 기존 list를 인자로 계속 쓰다보니 다시 가야하는 노드를 가지 않는 오류를 발생하여 아에 새로 할당하여 그것만 사용했다.