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

2022 KAKAO BLIND RECRUITMENT > 양과늑대

---

양과 늑대

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

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

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

2022 카카오 신입공채 1차 온라인 코딩테스트 for Tech developers 문제해설

 

 

문제에 대한 해설은 카카오 신입공채 테크블로그의 해설이 워낙 잘 설명되어 있으므로, 이 글로 대체하겠습니다.

 

   static int[] Info;
    static int[][] Edges;
    static int max = 0;
    static List<Tree> trees = new ArrayList<>();

    public static int solution(int[] info, int[][] edges) {
        Info = info;
        Edges = edges;
        for (int i = 0; i < info.length; i++) {
            int left = -1;
            int right = -1;
            for (int[] edge : edges) {
                if (edge[0] == i) {
                    if (left == -1) {
                        left = edge[1];
                    } else {
                        right = edge[1];
                        break;
                    }
                }
            }
            trees.add(new Tree(info[i] == 0, left, right));
        }

        checkMaxSheep(0, 0, 0, new ArrayList<>(), new boolean[info.length]);

        return max;
    }

    private static void checkMaxSheep(int now, int sheep, int wolf, ArrayList<Integer> canMove,
        boolean[] visit) {
        if (Info[now] == 0) {
            sheep++;
        } else {
            wolf++;
        }
        ArrayList<Integer> tmp = new ArrayList<>(canMove);
        boolean[] tmpVisit = Arrays.copyOf(visit, visit.length);
        if (sheep > wolf) {
            max = Math.max(max, sheep);
            tmpVisit[now] = true;
            int left = trees.get(now).left;
            if (left != -1) {
                tmp.add(left);
            }
            int right = trees.get(now).right;
            if (right != -1) {
                tmp.add(right);
            }
            for (int go : tmp) {
                if (tmpVisit[go]) {
                    continue;
                }
                checkMaxSheep(go, sheep, wolf, tmp, tmpVisit);
            }
        }
    }

    static class Tree {

        boolean isSheep;
        int left;
        int right;

        public Tree(boolean isSheep, int left, int right) {
            this.isSheep = isSheep;
            this.left = left;
            this.right = right;
        }
    }