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

코드 힌트

1. 인접 행렬 사용:
   • map 배열은 전선의 연결 상태를 기록하는 인접 행렬로, 두 노드가 연결되면 map[i][j] = 1로 설정합니다.
2. 전선 끊기:
   • 모든 전선을 하나씩 끊어보고 각 경우에 대해 두 네트워크로 나누어진 후, 그 크기 차이를 계산합니다.
   • cutWire() 함수에서 끊은 전선은 다시 복구됩니다.
3. DFS(깊이 우선 탐색):
   • DFS를 이용하여 한 네트워크의 노드 개수를 계산합니다. 한쪽 네트워크를 탐색한 후, 나머지 네트워크의 크기는 전체에서 빼는 대신 다시 탐색합니다.
4. 최솟값 계산:
   • 각 전선을 끊었을 때 두 네트워크의 크기 차이를 계산하고, 그 차이의 최솟값을 갱신합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    
    // 방문 여부를 체크하는 배열
    static boolean[] visit;
    // 연결 정보를 저장하는 인접 행렬
    static int[][] map;
    // 두 네트워크의 크기 차이의 최솟값을 저장하는 변수
    static int result = Integer.MAX_VALUE;
    
    // 주어진 전선 정보(wires)를 기반으로 네트워크를 두 개로 나누었을 때,
    // 두 네트워크의 크기 차이의 최솟값을 구하는 함수
    public int solution(int n, int[][] wires) {
        map = new int[n][n]; // 인접 행렬 초기화
        
        // 주어진 전선 정보를 인접 행렬에 저장
        for (int[] wire : wires) {
            map[wire[0]-1][wire[1]-1]++; // 1번 노드 기준으로 연결
            map[wire[1]-1][wire[0]-1]++; // 2번 노드 기준으로 연결
        }
        
        // 모든 전선을 하나씩 끊어보고 네트워크의 크기 차이의 최솟값을 계산
        cutWire(n);
        
        return result; // 계산된 최솟값 반환
    }
    
    // 전선을 하나씩 끊으면서 네트워크를 두 개로 나누고 크기 차이를 계산하는 함수
    void cutWire(int n) {
        // 모든 노드 간의 연결을 확인
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 두 노드가 연결된 전선이 있다면
                if (map[i][j] == 1) {
                    // 전선을 끊음 (연결을 끊음)
                    map[i][j] = 0;
                    map[j][i] = 0;
                    
                    // 방문 배열 초기화
                    visit = new boolean[n];
                    
                    // 첫 번째 네트워크의 크기 계산 (전선을 끊은 후 한쪽 네트워크)
                    int count1 = dfs(i, n);
                    
                    // 두 번째 네트워크의 크기 계산 (전선을 끊은 후 다른 한쪽 네트워크)
                    int count2 = dfs(j, n);
                    
                    // 두 네트워크의 크기 차이 계산 후 최솟값 갱신
                    result = Math.min(result, Math.abs(count1 - count2));
                    
                    // 끊었던 전선을 다시 복구
                    map[i][j] = 1;
                    map[j][i] = 1;
                }
            }
        }
    }
    
    // DFS를 이용해 한 네트워크의 노드 개수를 계산하는 함수
    int dfs(int idx, int n) {
        visit[idx] = true; // 현재 노드를 방문 처리
        int count = 1; // 현재 노드도 카운트에 포함
        
        // 인접한 노드들을 순회하며 연결된 노드를 재귀적으로 탐색
        for (int i = 0; i < n; i++) {
            if (!visit[i] && map[idx][i] == 1) {
                count += dfs(i, n); // 연결된 노드의 개수를 더함
            }
        }
        return count; // 네트워크에 속한 모든 노드의 개수를 반환
    }
}