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

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

코딩테스트 연습 - 전력망을 둘로 나누기

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public int solution(int n, int[,] wires)
    {
        int answer = -1;
        int[] _count = new int[2];
        List<int> _link1 = new List<int>();
        List<int> _link2 = new List<int>();
        List<int> _abs = new List<int>();

        for (int i = 0; ++i < n;)
        {
            for (int j = -1; ++j < wires.GetLength(0);)
                if (wires[j, 0] == i)
                {
                    _link1.Add(wires[j, 1]);
                    GetAbs(wires, i, _link1, _count, 0);

                    _link2.Add(i);
                    GetAbs(wires, wires[j, 1], _link2, _count, 1);

                    _abs.Add(Math.Abs(_count[0] - _count[1]));

                    Array.Clear(_count, 0, 2);
                    _link1.Clear(); _link2.Clear();
                }
        }

        answer = _abs.Min();
        return answer;
    }

    void GetAbs(int[,] wires, int curV, List<int> link, int[] count, int index)
    {
        for (int j = -1; ++j < wires.GetLength(0);)
            if (wires[j, 0] == curV || wires[j, 1] == curV)
            {
                int next = wires[j, 0] == curV ? wires[j, 1] : wires[j, 0];

                if (!link.Contains(next))
                {
                    link.Add(curV);
                    count[index] += 1;
                    GetAbs(wires, next, link, count, index);
                }
            }
    }
}

1부터 쭉 돌면서(DFS, BFS) 연결된 부분 자르고 나머지 연결되어있는 부분 개수 구해서 빼고 절댓값 취하고 다 돌고 난 뒤에 가장 작은 절댓값이 답이 돼버리는 문제

 

지금 보니까 진짜 더럽게 푼 느낌이구만....

뭐 어쨌든!

나름 알고리즘도 생각해야 하고 음음 재밌는 문제

DFS, BFS의 내용은 널리고 널렸으니꼐..

근데 항상 대부분 깊이 우선으로 푼 거 같은데 앞으로 너비 우선 방식으로도 좀 풀어봐야겠다..