HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
👻
개발 기록/
코딩테스트 스터디
코딩테스트 스터디/
Minimum Time to Collect All Apples in a Tree

Minimum Time to Collect All Apples in a Tree

Link
https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/
Deadline
Feb 1, 2023
Status
Archived
Type
Hash Table
Tree
DFS
BFS
Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.
The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.
notion image
Example 3:
Constraints:
  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai < bi <= n - 1
  • hasApple.length == n

풀이

재영
효성 https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/solutions/3033250/dfs-detailed-explanation/
리팩터링 with 재영
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
Output: 0

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {boolean[]} hasApple
 * @return {number}
 */
const minTime = function (n, edges, hasApple) {
  let result = 0;

  const graph = Array.from({ length: n }, () => []);
  edges.forEach(([s, e]) => {
    graph[s].push(e);
    graph[e].push(s);
  });

  const dfs = (node, prev) => {
    let shouldGo = hasApple[node];

    for (const next of graph[node]) {
      if (next !== prev) {
        const childHasApple = dfs(next, node);

        if (childHasApple) {
          shouldGo = true;
          result += 2;
        }
      }
    }

    return shouldGo;
  };

  dfs(0, null);

  return result;
};
var minTime = function (n, edges, hasApple) {
    const children = new Array(n);
    for (let i = 0; i < n; i++) {
        children[i] = new Array();
    }
    for (let edge of edges) {
        children[edge[0]].push(edge[1]);
        children[edge[1]].push(edge[0]);
    }

    let res = 0;
    const dfs = (node, parent) => {
        let val = false;
        for (let child of children[node]) {
            if (child === parent) continue;
            res++;
            const isChildHasApple = dfs(child, node);
            isChildHasApple ? res++ : res--;
            val = val || isChildHasApple;
        }
        return hasApple[node] ? true : val;
    }
    dfs(0);

    return res;
};
var minTime = function (n, edges, hasApple) {
    const children = new Array(n);
    for (let i = 0; i < n; i++) {
        children[i] = new Array();
    }
    for (let edge of edges) {
        children[edge[0]].push(edge[1]);
        children[edge[1]].push(edge[0]);
    }

    let res = 0;
    const dfs = (node, parent) => {
        let val = false;
        for (let child of children[node]) {
            if (child === parent) continue;
            const isChildHasApple = dfs(child, node);
            if(isChildHasApple) {
                res += 2;
                val = true;
            }
        }
        return hasApple[node] ? true : val;
    }
    dfs(0);

    return res;
};