(C#) 모두 0으로 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/76503?language=csharp

프로그래머스

 

1. 그래프를 인접 리스트로 표현하기

 edges가 간선 리스트 형태로 들어오는데, 이런 형태로는 그래프를 순회하기 어렵다.

 따라서 간선 리스트 형태의 표현을 인접 리스트 형태로 바꾸었다.

 

2. 재귀함수로 풀기

 주어진 그래프는 반드시 트리 형태이므로, 트리의 말단으로부터 값을 전파하며 루트 노드까지 도달한다면 원하는 답을 구할 수 있다.

 나는 트리의 말단으로부터 작업을 수행하는 대신 재귀 방식으로 문제를 풀었다.

 

 어떤 노드 n을 루트로 하는 서브트리의 모든 노드의 가중치의 합을 구하는 함수 foo(n)을 정의한다.

 어떤 노드 n의 값을 0으로 하기 위해서는 n의 자식노드들 n1, n2, ... nx에 대해서 foo(n1), foo(n2), ... foo(nx)의 값들을 더해주면 된다.

 이 과정에서 전역으로 정의한 answer의 값에 Math.Abs(foo(n))을 더해 갱신해준다.

 

 이를 루트노드 0으로부터 재귀하면 최종적으로 원하는 답을 구할 수 있다.

 

 다만 재귀함수를 정의하고 사용하기 위해 전역 변수를 선언했다. 깔끔하지 않은 느낌이 들어 찝찝하다.

코드

using System;
using System.Collections.Generic;

public class Solution {
    long answer = 0;
    long[] a;
    bool[] visited;
    List<int>[] graph;
    
    public long solution(int[] a, int[,] edges)
    {
        this.a = new long[a.Length];
        for(var i = 0; i < a.Length; i++){
            this.a[i] = a[i];
        }
        long sum = 0;
        for (var i = 0; i < a.Length; i++)
        {
            sum += a[i];
        }
        if (sum != 0) return -1;

        graph = new List<int>[a.Length];
        int[] count = new int[a.Length];

        // 인접 리스트
        for (var i = 0; i < edges.GetLength(0); i++)
        {
            if (graph[edges[i, 0]] == null)
                graph[edges[i, 0]] = new List<int>();
            if (graph[edges[i, 1]] == null)
                graph[edges[i, 1]] = new List<int>();

            count[edges[i, 0]]++;
            count[edges[i, 1]]++;
            graph[edges[i, 0]].Add(edges[i, 1]);
            graph[edges[i, 1]].Add(edges[i, 0]);
        }
        
        visited = new bool[a.Length];
        visited[0] = true;

        foo(0);
        return answer;
    }

    long foo(int n)
    {
        var sum = a[n];
        for (var i = 0; i < graph[n].Count; i++)
        {
            var next = graph[n][i];
            if (visited[next]) continue;
            visited[next] = true;
            var s = foo(next);
            answer += Math.Abs(s);
            sum += s;
            a[n] += s;
        }
        return sum;
    }
}