[프로그래머스 C#] Lv.2 전력망을 둘로 나누기

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

프로그래머스

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

트리 형태의 전력망에서 전선(간선)을 하나 끊었을 때 생기는 두 전력망의 송전탑(정점)의 개수 차이의 최소 값을 구하는 문제

 

1) 간선을 하나 끊어서 나오는 두 전력망의 송전탑 개수의 차이 X 구하기

 - n = a + b, X = | a - b | 를 연립 -> X = | n - 2a | = | n - 2b | 

 -> 즉, 한 쪽의 송전탑 개수만 구하면 차이를 알 수 있음

 

2) 최소 값 찾는 방법 (아이디어)

- 임의의 정점 하나를 최상위 부모 노드로 봤을 때 전력망을 둘로 나눈다는 건 부모 노드와 자식 노드 간의 간선을 끊었을 경우로 봄

 -> 이 때, 자식 노드를 기준으로 자식 노드의 개수 + 1은 두 전력망 중의 하나의 송전탑 개수가 됨을 이용

 

3) 자식 노드의 개수 구하기

- DFS 알고리즘을 이용해 현재 탐색 중인 노드가 만약 자식 노드가 있다면 자식 노드에게 개수를 받아오는 연산을 우선 처리하고 현재 탐색되는 노드가 자식 노드에게 개수를 다 받아왔다면 개수를 파악해 최소 값 갱신

 -> 자식 노드의 여부는 간선 그래프를 담은 dict과 방문배열로 체크

 

https://godgjwnsgur7.tistory.com/47

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

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public int solution(int n, int[,] wires)
        {
            int answer = int.MaxValue;

            // 인덱스와 각 노드 번호를 맞추기 위해 + 1을 하고 0번 인덱스를 사용하지 않음
            var boolArray = new bool[n + 1]; // 방문배열
            var intArray = new int[n + 1]; // 자식노드의 개수 + 1을 담는 배열
            var dict = new Dictionary<int, List<int>>(); // 간선 그래프

            // 초기 값 세팅
            for (int i = 1; i <= n; i++)
            {
                intArray[i] = 1;
                dict.Add(i, new List<int>());
            }

            // 간선 그래프 초기화
            for (int i = 0; i < wires.GetLength(0); i++)
            {
                dict[wires[i, 0]].Add(wires[i, 1]);
                dict[wires[i, 1]].Add(wires[i, 0]);
            }

            // 1번 인덱스를 최상위 부모노드로 두고 DFS 탐색
            DFS(1, 1, n, intArray, boolArray, dict, ref answer);

            return answer;
        }

        public void DFS(int currIndex, int parentIndex, int n, int[] intArray, bool[] boolArray, Dictionary<int, List<int>> dict, ref int answer)
        {
            boolArray[currIndex] = true;

            // 자식 노드의 개수를 받아옴
            foreach (int childIndex in dict[currIndex])
                if (boolArray[childIndex] == false)
                    DFS(childIndex, currIndex, n, intArray, boolArray, dict, ref answer);

            // 모든 자식 노드의 개수를 받아왔다면
            int count = Math.Abs(n - (intArray[currIndex] * 2)); // 두 전력망 개수 차이
            answer = Math.Min(answer, count); // 더 작을 경우 갱신
            intArray[parentIndex] += intArray[currIndex]; // 부모 노드에게 전달
        }
    }