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

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

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

[문제]

[풀이]

처음엔 트리 DP 문제인줄 알고 접근했었다가 다시 돌아올 수 있다는 조건때문에 풀지 못했었다.
이 문제는 오히려 중복체크를 하지 않아도 되기때문에 그리디+탐색으로 충분히 풀 수 있었다.

1. 탐색 가능한 노드들을 묶어서 list (curPlan)에 push (초기엔 크기1인 루트노드만 있음)

2. DFS탐색. 탐색할때마다 현재 양의개수로 새롭게 MAX를 갱신. 종료조건은 늑대가 양보다 더 많거나 같을 경우
 2-1. DFS 탐색도중 현재노드 시점에서 더 많다면 그 현재노드와 연결된 모든 노드를 새로운 list (nextPlan)에 push
 2-2. 이전에 기록해둔 list (curPlan) 에서 자기자신을 제외한 나머지 노드들도 push

3. 새롭게 만든 list (nextPlan)을 순회하면서 재귀적으로 DFS 탐색

import java.util.*;
import java.io.*;
import java.util.stream.*;

class Solution {
    ArrayList<ArrayList<Integer>> graph;
    int answer;
    int[] info;

    public int solution(int[] info, int[][] edges) {
        initGraph(info, edges);
        answer = 0;
        List<Integer> plan = new ArrayList<>();
        plan.add(0);
        dfs(0,0,0,plan);
        return answer;
    }

    public void dfs(int cur,int sheep,int wolf,List<Integer> curPlan){

        if (info[cur] == 0) sheep++;
        else wolf++;

        if(wolf>=sheep) return;
        answer = Math.max(sheep,answer);

        List<Integer> nextPlan = new ArrayList<>(curPlan);
        nextPlan.remove((Integer)cur);
        nextPlan.addAll(graph.get(cur));

        for (Integer next : nextPlan)
            dfs(next,sheep,wolf,nextPlan);

    }

    private void initGraph(int[] info, int[][] edges) {
        graph = new ArrayList<>();

        IntStream.range(0, info.length)
                .forEach(e->graph.add(new ArrayList<>()));

        Arrays.stream(edges).forEach(e-> graph.get(e[0]).add(e[1]));
        this.info = info;
    }
}