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

20 Nov 2023 in Algorithm on 그래프 이론

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

풀이

늑대의 수가 양의 수 이상이 되면 양들이 다 잡아먹혀서 안된다.

트리의 0번부터 시작해서 양을 늑대보다 많게 하면서 돌아다닌다. 이때 양의 최댓값을 찾아야한다.

이동이 가능한 노드들을 담는 리스트를 만들었다. 특정 노드를 방문 할 때 그 노드의 자식 노드를 리스트에 담고, 해당 노드는 제거해주었다.

이동가능한 리스트를 들고 dfs탐색을 통해 최댓값을 갱신했다.

리스트에서 노드를 제거할 때 ConcurrentModificationException 때문에 고생한 문제였다.

관련글 : ConcurrentModificationException

---

메모리: 70.6MB

시간: 4.22ms

언어: Java 11

코드

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

class Solution {
    static int answer;
    public int solution(int[] info, int[][] edges) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for(int i = 0; i < info.length; i++) {
            list.add(new ArrayList<>());
        }
        for(int i = 0; i < edges.length; i++) {
            list.get(edges[i][0]).add(edges[i][1]);
        }

        List<Integer> possibleNext = new ArrayList<>();
        possibleNext.add(0);

        answer = 0;
        dfs(0, possibleNext, list, info, 0, 0);

        return answer;
    }

    private static void dfs(int node, List<Integer> possibleNext, ArrayList<ArrayList<Integer>> list, int[] info, int sheep, int wolf) {
        if(info[node] == 0) {
            sheep++;
        }else {
            wolf++;
        }

        if(sheep <= wolf) {
            return;
        }

        answer = Math.max(answer, sheep);

        possibleNext = possibleNext.stream()
            .filter(item -> item != node)
            .collect(Collectors.toList());

        for(int nextNode : list.get(node)) {
            possibleNext.add(nextNode);
        }

        for(int next : possibleNext) {
            dfs(next, possibleNext, list, info, sheep, wolf);
        }
    }
}