[프로그래머스 C#] Lv.3 모두 0으로 만들기

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 조건에 따라 최적의 연산 횟수로 모든 정점의 가중치를 0으로 만드는 최소 연산 횟수를 구하는 문제

 

0) 주어진 조건에 따른 연산

- 인접한 두 노드 a, b에 각각 -1, 1을 더할 수 있음

 -> b += a, a = 0 또는 a += b, b = 0 과 같음 (마치 이동, 전달하듯)

 

1) 모든 정점의 가중치를 0으로 만들 수 없는 경우

- 0번에 의해 마치 값을 전달하듯 연산하는 것

 -> 모든 정점의 값을 더한 값이 0이 되지 않으면 모든 가중치를 0으로 만들 수 없음

 

2) 최적의 연산 횟수 구하는 방법

- 트리구조이기 때문에 임의의 정점을 최상위 부모 노드로 두고 가장 멀리있는 최하위 노드에서부터 최상위 노드로 값을 전달하며 연산 횟수를 카운트하면 됨

-> 결국 최상위 부모 노드로 모여 상쇄되며 0이 될 것

( 최상위 부모 노드는 존재하는 노드라면 어떤 값이든 상관 없으므로 반드시 존재하는 0으로 지정 )

 

DFS 알고리즘을 이용해 최하위노드 -> 루트 부모 노드 방향으로 연산해 값을 산출

 

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public long solution(int[] a, int[,] edges)
        {
            long answer = 0;
            var dict = new Dictionary<int, List<int>>(); // 양방향 간선 그래프
            var nodeArray = new long[a.Length]; // 노드배열(정점배열) : (long)a[]
            var boolArray = new bool[a.Length]; // 방문배열

            // 각 배열, 사전 초기화
            long total = 0; // 모든 노드의 총합
            for (int i = 0; i < a.Length; i++)
            {
                dict.Add(i, new List<int>());
                nodeArray[i] = (long)a[i];
                total += nodeArray[i];
            }

            // 모든 노드의 총합이 0이 되지 않으면 모든 가중치를 0으로 만들 수 없음
            if (total != 0)
                return -1;

            // 양방향 간선 그래프 세팅
            for (int i = 0; i < edges.GetLength(0); i++)
            {
                dict[edges[i, 0]].Add(edges[i, 1]);
                dict[edges[i, 1]].Add(edges[i, 0]);
            }

            // DFS (모든 자식 노드 -> 루트 부모 노드 0으로 값 전달 / 트리구조)
            DFS(0, 0, nodeArray, boolArray, dict, ref answer);

            return answer;
        }

        // 모든 자식 노드의 값을 루트 부모 노드에게 전달하며 전달 횟수를 기록하는 메서드
        public void DFS(int currIndex, int parentIndex, long[] nodeArray, bool[] boolArray
                        , Dictionary<int, List<int>> dict, ref long answer)
        {
            boolArray[currIndex] = true;

            // 자식 노드 -> 부모 노드 로 값 이동
            foreach (int childIndex in dict[currIndex])
                if (boolArray[childIndex] == false)
                    DFS(childIndex, currIndex, nodeArray, boolArray, dict, ref answer);

            // 모든 자식 노드에게 값을 받아왔다면 부모노드에게 값을 전달하고 전달한 횟수를 기록
            answer += Math.Abs(nodeArray[currIndex]);
            nodeArray[parentIndex] += nodeArray[currIndex];
        }
    }