<Lv.3> 모두 0으로 만들기 (프로그래머스 : C#)

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

📕 문제 설명

트리의 모든 점들의 가중치를 0으로 만들 때 다음 연산의 최소 횟수 반환하기

=> 임의의 연결된 두 점을 골라 한쪽은 1을 증가시키고, 다른 한쪽은 1을 감소 시킨다.

• Input
  트리 각 점의 가중치 배열, 간선 정보
• Output
  트리 모든 점 가중치를 0으로 만드는 것이 불가능하면 -1, 가능하다면 최소 횟수 반환

예제

풀이

leaf쪽부터 자신의 값들을 parent쪽으로 넘겨주는 식으로 해서 최종적으로 처음 값으로 지정한 노드로 연산이 필요한 횟수가 모이는 식

using System;
using System.Collections.Generic;

public class Solution {
    long answer = 0;
    long[] longA;
    public long solution(int[] a, int[,] edges) {
        long sum = 0;
        int n = a.Length;
        
        longA = new long[n];
        List<long>[] graph = new List<long>[n];
        for (int i = 0; i < n; i++)
        {
            sum += a[i];
            longA[i] = (long)a[i];
            graph[i] = new List<long>();
        }
        
        if (sum != 0) return -1; // 전체 가중치 합을 0으로 못 만드는 경우
        
        // 인접 리스트 초기화
        for (int i = 0; i < edges.GetLength(0); i++)
        {
            long firstNode = (long)edges[i, 0];
            long secondNode = (long)edges[i, 1];
            graph[firstNode].Add(secondNode);
            graph[secondNode].Add(firstNode);
        }
        
        bool[] visited = new bool[n]; 
        DFS(0, 0, graph, visited);
        return answer;
    }
    
    public void DFS(long currNode, long parentNode, List<long>[] graph, bool[] visited)
    {   
        visited[currNode] = true;
        
        foreach(int adjNode in graph[currNode])
        {
            if (!visited[adjNode])
            {
                DFS(adjNode, currNode, graph, visited);
            }
        }
        
        answer += (long)Math.Abs(longA[currNode]);
        longA[parentNode] += longA[currNode];
        longA[currNode] = 0;
    }
}

결과