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

문제 살펴보기

1. n개의 송전탑이 하나의 트리 형태로 연결되어 있습니다.
2. 연결된 상태를 wires로 나타냅니다.
3. 하나의 연결 상태를 끊을 때 나뉘어지는 전력망의 수가 가장 비슷한 경우의 차이값을 구하세요.

제한사항

• 2 ≤ n ≤ 100

입출력 예

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

 

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int n, int[,] wires) {
        int answer = int.MaxValue;
        
        for(int i = 0; i < wires.GetLength(0); i++)
        {
            List<int> connect = new List<int>();
            connect.Add(wires[i, 0]);
            
            int size = DFS(i, wires, ref connect);
            
            Console.Write("size = " + size + " // " );
            foreach(int c in connect) Console.Write(c + " ");
            Console.Write("\n");
            
            int result = Math.Abs(size - (n - size));
            if(result < answer) answer = result;
        }
        
        
        
        return answer;
    }
    
    int DFS(int n, int[,] wires, ref List<int> connect){
        
        for(int i = 0; i < wires.GetLength(0); i++)
        {
            if(n == i) continue;
            
            if(connect.Contains(wires[i, 0]) && !connect.Contains(wires[i, 1]))
            {
                connect.Add(wires[i, 1]);
                DFS(n, wires, ref connect);
            }
            else if(connect.Contains(wires[i, 1]) && !connect.Contains(wires[i, 0]))
            {
                connect.Add(wires[i, 0]);
                DFS(n, wires, ref connect);
            }
        }
        
        return connect.Count;
    }
    
}

---