[Programmers][level3] 모두 0으로 만들기 (Kotlin)

[Programmers][level3] 모두 0으로 만들기 (Kotlin)

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

[난이도] level3

[유형] DFS

[풀이]

트리의 리프노드에서부터 자신을 0으로 만들고, 나머지를 부모 노드로 전달했을 때,

최종으로 값을 전달받는 루트노드가 0이 된다면 조건을 만족하는 것입니다.

DFS를 통해 리프부터 값을 누적해갈 수 있으며 각 노드의 return 이전에 연산 횟수를 더해주면 됩니다.

import java.util.* import kotlin.math.abs const val mxN = 300000 var adj = Array(mxN){ mutableListOf()} 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): 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

from http://leesh111112.tistory.com/287 by ccl(A) rewrite - 2021-08-15 17:00:19