Daily LeetCode Challenge - 1443. Minimum Time to Collect All Apples in a Tree

Problem From.

https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/

오늘 문제는 undirectional tree 를 만드는 edges 배열이 주어지고, 각 node 에 사과가 있는지 없는지 표현하는 hasApple 배열이 주어졌을때, 각 노드를 돌며 사과가 있으면 줏어오고, 사과가 있는 노드만을 방문하며 사과를 줏어오는 최단 시간을 구하는 문제였다. 각 노드를 이동하는 시간은 1초로 동일했다.

먼저 mutableList 를 원소로 가지는 n 개의 원소를 가진 graph 리스트를 만들어서, edges 를 tree의 형식으로 바꾸었다. 그리고 dfs 를 사용하여 각 node 를 방문할 때 사과가 있으면 왕복하는 시간인 2초를 더해주었다.

class Solution {
    fun minTime(n: Int, edges: Array<IntArray>, hasApple: List<Boolean>): Int {
        val visited = BooleanArray(n)
        val graph = Array(n) { mutableListOf<Int>() }

        edges.forEach { (s, d) ->
            graph[s].add(d)
            graph[d].add(s)
        }

        fun dfs(vertices: MutableList<Int>, i: Int) : Int{ 
            if (visited[i]) {
                return 0
            }
            visited[i] = true 
            
            var total = 0
            vertices.forEach { v -> 
                total += dfs(graph[v], v)
            }
            if (i != 0 && (hasApple[i] || total != 0)) {
                total += 2
            }
            return total
        }

        return dfs(graph[0], 0)
    }
}

위 문제의 시간복잡도는 O(n) 이 된다.