C# 전력망을 둘로 나누기 - 완전탐색DFS / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/86971

 

 

나의 풀이

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

    for(int i = 0; i < wires.GetLength(0); ++i)
    {
        int a = wires[i, 0];
        int b = wires[i, 1];
        var setA = new HashSet<int>();
        setA.Add(a);
        var setB = new HashSet<int>();
        setB.Add(b);

        FindConnect(wires, setA, a, i);
        FindConnect(wires, setB, b, i);

        int diff = Math.Abs(setA.Count - setB.Count);
        if(diff < answer)
            answer = diff;                
    }

    return answer;
}

private void FindConnect(int[,] wires, HashSet<int> hashSet, int find, int except)
{
    for(int k = 0; k < wires.GetLength(0); ++k)
    {
        if(k == except)
            continue;

        if(hashSet.Contains(wires[k, 0]) && !hashSet.Contains(wires[k, 1]))
        {
            hashSet.Add(wires[k, 1]);
            FindConnect(wires, hashSet, wires[k, 1], except);
        }
        if(hashSet.Contains(wires[k, 1]) && !hashSet.Contains(wires[k, 0]))
        {
            hashSet.Add(wires[k, 0]);
            FindConnect(wires, hashSet, wires[k, 0], except);
        }
    }
}

그래프를 먼저 그리고 체크하는 방법도 있을 것이고

루프로 체크하는 방법도 있을듯.

 

루프로 하나씩 간선을 제외하면서 체크하는 방법을 썼다.  

시간복잡도가 꽤 클것 같은데 테스트도 통과된거 보면 느슨한 문제인듯.