113. 전력망을 둘로 나누기

 

오랜만에 C#으로 다시 문제를 풀기 시작했다~ 

 

최근에 Java로 코딩을 연습해야 할 일이 생겨서

 

Java로 문제를 풀고 있었다.

 

기본 틀 :

using System;

public class Solution {
    public int solution(int n, int[,] wires) {
        int answer = -1;
        return answer;
    }
}

 

wires에 연결된 point - point가 중구난방으로 작성 돼 있기 때문에

 

Dictionary와 HashSet으로 정리해줬다.

        Dictionary<int, HashSet<int>> dict = new Dictionary<int, HashSet<int>>();
        
        // point 간 연결이 2개인 경우를 대비해서 Dictionary와 HashSet 사용
        for(int i = 0; i < wires.GetLength(0); i++)
        {
            for(int j = 0; j < wires.GetLength(1); j++)
            {
                int point1 = wires[i, 0], point2 = wires[i, 1];
                if(!dict.ContainsKey(point1)) dict[point1] = new HashSet<int>();
                
                dict[point1].Add(point2);
                
                if(!dict.ContainsKey(point2)) dict[point2] = new HashSet<int>();
                
                dict[point2].Add(point1);
            }
        }

 

Value로 HashSet을 사용한 이유는 위의 코드가 value 값이 2번 저장되는 오류가 발생하기 때문이다.

 

ex) 1 - 3 

 

key : 1, value : 3

 

dict[1].Add(3);

dict[3].Add(1);

 

key : 3, value : 1

 

dict[3].Add(1);

dict[1].Add(3);

 

이제부터는 점과 점의 연결을 끊으면서 원하는 결과를 도출해야 하기 때문에

 

int min = int.MaxValue;

for(int i = 0; i < wires.GetLength(0); i++)
{
	int point1 = wires[i, 0], point2 = wires[i, 1];
}

 

위와 같이 두 점을 지정하고

        int min = int.MaxValue;
        
        for(int i = 0; i < wires.GetLength(0); i++)
        {
            int point1 = wires[i, 0], point2 = wires[i, 1];
            
            // 연결 해제
            dict[point1].Remove(point2);
            dict[point2].Remove(point1);
            
            
            // ...
            
            
            // 다음 진행을 위해 다시 연결
            dict[point1].Add(point2);
            dict[point2].Add(point1);
        }

 

위와 같이 Dictionary에서 연결 여부를 제거해줬다.

 

하지만, 다음 반복에서는 다시 연결이 돼 있어야 하기 때문에 반복문의 제일 아래에 다시 연결 정보를 추가해줬다. 

 

... 에는

 

연결을 끊은 두 그래프의 연결 개수를 구해야 하기 때문에

 

            int count = BFS(dict, point1, n);
            
            // n - count로 연결이 끊긴 포인트의 연결 개수에서
            // - count로 차이 구하기
            int diff = Math.Abs((n - count) - count);
            
            if(diff < min) min = diff;

 

위와 같이 코드를 작성 했는데 그 이유는

 

하나의 그래프를 구한 후 매개변수로 제공되는 n을 이용해 

 

다른 그래프의 연결 개수를 구할 수 있기 때문이다.

 

BFS 함수는 넓이 우선 탐색이라

 

public int BFS(Dictionary<int, HashSet<int>> dict, int point1, int n)
{
	bool[] visited = new bool[n + 1];
    	Queue<int> queue = new Queue<int>();
    	int count = 0;
    
    // ...
    
}

 

Queue가 반드시 필요하기 때문에 만들어주고 방문 여부를 구분하기 위해 visited 변수를 만들어줬다.

 

	queue.Enqueue(point1);
        visited[point1] = true;

 

그 후, 처음 시작 점을 queue에 추가해주고 방문 여부를 기록한 후

 

        while(queue.Count > 0)
        {
            int current = queue.Dequeue();
            count++;
            
            foreach(var nextPoint in dict[current])
            {
                if(!visited[nextPoint])
                {
                    visited[nextPoint] = true;
                    queue.Enqueue(nextPoint);
                }
            }
        }
        
        return count;

 

while문에서 해당 점을 꺼내 해당 점과 연결된 모든 점을 queue에 담고 방문 여부를 변경해줬다.

 

while문이 끝나면 하나의 그래프에 연결된 점의 개수를 return 해주었다.

 

전체 코드 :

using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;

public class Solution {
    public int solution(int n, int[,] wires) 
    {
        Dictionary<int, HashSet<int>> dict = new Dictionary<int, HashSet<int>>();
        
        // point 간 연결이 2개인 경우를 대비해서 Dictionary와 HashSet 사용
        for(int i = 0; i < wires.GetLength(0); i++)
        {
            for(int j = 0; j < wires.GetLength(1); j++)
            {
                int point1 = wires[i, 0], point2 = wires[i, 1];
                if(!dict.ContainsKey(point1)) dict[point1] = new HashSet<int>();
                
                dict[point1].Add(point2);
                
                if(!dict.ContainsKey(point2)) dict[point2] = new HashSet<int>();
                
                dict[point2].Add(point1);
            }
        }
        
        int min = int.MaxValue;
        
        for(int i = 0; i < wires.GetLength(0); i++)
        {
            int point1 = wires[i, 0], point2 = wires[i, 1];
            
            // 연결 해제
            dict[point1].Remove(point2);
            dict[point2].Remove(point1);
            
            int count = BFS(dict, point1, n);
            
            // n - count로 연결이 끊긴 포인트의 연결 개수에서
            // - count로 차이 구하기
            int diff = Math.Abs((n - count) - count);
            
            if(diff < min) min = diff;
            
            // 다음 진행을 위해 다시 연결
            dict[point1].Add(point2);
            dict[point2].Add(point1);
        }
        
        return min;
    }
    
    public int BFS(Dictionary<int, HashSet<int>> dict, int point1, int n)
    {
        bool[] visited = new bool[n + 1];
        Queue<int> queue = new Queue<int>();
        int count = 0;
        
        queue.Enqueue(point1);
        visited[point1] = true;
        
        while(queue.Count > 0)
        {
            int current = queue.Dequeue();
            count++;
            
            foreach(var nextPoint in dict[current])
            {
                if(!visited[nextPoint])
                {
                    visited[nextPoint] = true;
                    queue.Enqueue(nextPoint);
                }
            }
        }
        
        return count;
    }
}