Leetcode 1443. Minimum Time to Collect All Apples in a Tree

難易度

Medium

アプローチ

DFS

import java.util.ArrayList;
import java.util.List;

public class MinimumTimeToCollectAllApplesInATree1443 {
    public static void main(String[] args) {

        int n = 7;
        int[][] edges = {{0, 1}, {0, 2}, {1, 4}, {1, 5}, {2, 3}, {2, 6}};
        List<Boolean> hasApple = new ArrayList<>();

        hasApple.add(false);
        hasApple.add(false);
        hasApple.add(true);
        hasApple.add(false);
        hasApple.add(true);
        hasApple.add(true);
        hasApple.add(false);

        int a = minTime(n, edges, hasApple);
        System.out.println(a);

    }


    public static boolean[] isVisited;
    public static ArrayList<ArrayList<Integer>> tree;
    public static int result = 0;

    public static int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        isVisited = new boolean[n];

        tree = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tree.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int start = edge[0];
            int end = edge[1];

            tree.get(start).add(end);
            tree.get(end).add(start);
        }

        result = dfs(0, hasApple);
        return result;

    }

    public static int dfs(int edge, List<Boolean> hasApple) {
        if (isVisited[edge]) {
            return 0;
        }

        isVisited[edge] = true;

        int count = 0;
        for (int i = 0; i < tree.get(edge).size(); i++) {
            int next = tree.get(edge).get(i);
            count += dfs(next, hasApple);
        }

        // 現在のedgeが0の場合、現在のカウントを返す
        if (edge == 0) {
            return count;
        }

        // 現在のedgeがりんご又はカウントされた場合、パスの追加のため、+ 2
        if (hasApple.get(edge) || count > 0) {
            return 2 + count;
        }
        
        // 他の場合、0をReturnする
        return 0;
        
    }

/* WA
    public static int dfs_WA(int edge, int count, List<Boolean> hasApple) {
        if (isVisited[edge]) {
            return 0;
        }

        isVisited[edge] = true;

        for (int i = 0; i < tree.get(edge).size(); i++) {
            int next = tree.get(edge).get(i);

            count += dfs(next, count + 1, hasApple);

        }
        count++;
        if (hasApple.get(edge)) {
            result = count;
        }
        return count;
    }
*/
}

• こちらを参考しました