[프로그래머스][level3] 모두 0으로 만들기 (Kotlin)

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

코딩테스트 연습 - 모두 0으로 만들기

 

 

[난이도] level3
[유형] DFS

[풀이]
트리의 리프노드에서부터 자신을 0으로 만들고, 나머지를 부모 노드로 전달했을 때,
최종으로 값을 전달받는 루트노드가 0이 된다면 조건을 만족하는 것입니다.
DFS를 통해 리프부터 값을 누적해갈 수 있으며 각 노드의 return 이전에 연산 횟수를 더해주면 됩니다.

 

import java.util.*
import kotlin.math.abs
const val mxN = 300000
var adj = Array(mxN){ mutableListOf<Int>()}
var b = LongArray(mxN)
var ans=0L
fun dfs(par:Int,n:Int):Long{
    var ret = b[n]
    for(i in 0..adj[n].size-1){
        if(adj[n][i]!=par) ret+=dfs(n,adj[n][i])
    }
    ans+=abs(ret)
    return ret
}
class Solution {
    fun solution(a: IntArray, edges: Array<IntArray>): Long {
        for(i in a.indices) b[i]=a[i].toLong()
        for((u,v) in edges){
            adj[u].add(v)
            adj[v].add(u)
        }
        if(dfs(-1,0)!=0L) ans=-1
        return ans
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/모두_0으로_만들기.cpp