問題の説明

に答える

初めての試み

結果

コード#コード#

import java.util.*;

class Solution {
    public int nodeCount, maxSheepCount;
    public int[] parents;
    public ArrayList<Integer>[] childs;

    public int solution(int[] info, int[][] edges) {
        nodeCount = info.length;

        // parents: 각 노드의 부모 노드 번호를 저장
        // childs: 각 노드의 자식 노드 번호들을 저장
        parents = new int[nodeCount];
        childs = new ArrayList[nodeCount];

        for (int[] link : edges) {
            int parent = link[0];
            int child = link[1];

            if (childs[parent] == null) {
                childs[parent] = new ArrayList<>();
            }

            parents[child] = parent;
            childs[parent].add(child);
        }

        // 방문체크하기 위한 배열 (visited[x][y] : x node에 sheepCount가 y일 때 방문 여부)
        boolean[][] visited = new boolean[nodeCount][nodeCount + 1];
        getAnimal(1, 0, 0, info, visited);

        return maxSheepCount;
    }

    // sheepCount: 양의 수, wolfCount: 늑대의 수, node: 현재 노드
    // animal: 동물들의 현재 상태(0: 양, 1: 늑대, -1: 이미 모아서 자리에 없음)
    public static void getAnimal(int sheepCount, int wolfCount, int node, int[] animal, boolean[][] visited) {
        if (sheepCount <= wolfCount || visited[node][sheepCount]) {
            return;
        }

        int[] copied = getCopied(animal);

        visited[node][sheepCount] = true;
        copied[node] = -1;
        maxSheepCount = Math.max(maxSheepCount, sheepCount);

        // 부모 노드로 다시 돌아간다
        getAnimal(sheepCount, wolfCount, parents[node], copied, visited);

        if (childs[node] == null) {
            return;
        }

        for (int nextNode : childs[node]) { // 다음에 방문할 노드
            if (copied[nextNode] == 0) { // 양
                getAnimal(sheepCount + 1, wolfCount, nextNode, copied, visited);
            } else if (copied[nextNode] == 1) { // 늑대
                getAnimal(sheepCount, wolfCount + 1, nextNode, copied, visited);
            } else { // 이미 모아서 자리에 없음
                getAnimal(sheepCount, wolfCount, nextNode, copied, visited);
            }
        }
    }

    public static int[] getCopied(int[] target) {
        int[] copied = new int[target.length];

        for (int i = 0; i < target.length; i++) {
            copied[i] = target[i];
        }

        return copied;
    }
}

2回目の試み

アイデア

結果

コード#コード#

import java.util.*;

class Solution {
    public int maxSheepCount;
    public ArrayList<Integer>[] childs;

    public int solution(int[] info, int[][] edges) {
        // childs: 각 노드의 자식 노드 번호들을 저장
        // childs[x] 에는 x 노드의 자식 노드들이 ArrayList에 저장되어 있다.
        childs = new ArrayList[info.length];

        for (int[] link : edges) {
            int parent = link[0];
            int child = link[1];

            // child가 parent의 첫 자식 노드이면 childs[parent]의 값이 null이다
            if (childs[parent] == null) {
                childs[parent] = new ArrayList<>();
            }

            childs[parent].add(child);
        }

        // dfs가 진행되면서 각 depth마다 다음에 방문할 노드들은 새로운 List를 만들어 넣어 주어야 한다.
        // 이렇게 하지 않으면 모든 depth에서 같은 nextNodes를 공유하게 된다.
        List<Integer> nextNodes = new ArrayList<>();
        nextNodes.add(0);
        getAnimal(0, 0, 0, nextNodes, info);

        return maxSheepCount;
    }

    // sheepCount: 양의 수, wolfCount: 늑대의 수, node: 현재 노드, nextNodes: 다음에 갈 수 있는 노드들
    public void getAnimal(int sheepCount, int wolfCount, int node, List nextNodes, int[] info) {
        // XOR 연산으로 info[node]가 0일 때는 sheepCount에 1이 더하고,
        // info[node]가 1일 때는 wolfCount에 1을 더한다.
        sheepCount += info[node] ^ 1;
        wolfCount += info[node];
        maxSheepCount = Math.max(maxSheepCount, sheepCount);

        if (sheepCount <= wolfCount) {
            return;
        }

        List<Integer> copied = new ArrayList<>();
        copied.addAll(nextNodes);
        // 현재 방문한 노드에서 갈 수 있는 자식 노드가 있다면 추가해준다.
        if (childs[node] != null) {
            copied.addAll(childs[node]);
        }
        // 현재 방문한 노드를 다음에 방문할 목록에서 삭제한다.
        copied.remove(Integer.valueOf(node));

        for (int nextNode : copied) { // 다음에 방문할 노드
            getAnimal(sheepCount, wolfCount, nextNode, copied, info);
        }
    }
}