프로그래머스 - 전력망을 둘로 나누기(JAVA)

마이구미·2025년 6월 1일

알고리즘 자바 프로그래머스

알고리즘

목록 보기

1/3

오늘은 알고리즘을 공부를 하면서 흥미로웠던 문제에 대해서 나누어 보고자 합니다.

바로 LV2 문제 중 하나인 '전력망을 둘로 나누기'입니다.

문제 요약

송전탑의 개수 n, 그리고 전선 정보 wires 이중 배열이 매개변수로 주어질 때 전선들 중 하나를 끊었을 때 나누어지는 두 전력망의 차이가 최소가 되도록 전력망을 분리하고 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 구하는 것이 목표입니다.

여기서 n은 $2$ 이상 $100$ 이하의 크기를 가지고 wires는 n-1의 크기를 가집니다. 이때 wires의 원소 [v1, v2]는 v1 송전탑과 v2 송전탑이 연결되어 있다는 의미입니다.

실행시간에 대한 제한이 없으며, 정확성에 대한 검사가 있으므로 완전탐색으로 진행하는 것이 가능합니다.

접근 방법

DFS를 이용하여 문제를 풀어봅시다.
1. 먼저 wires를 완전 탐색을 하기 쉬운 graph의 형태로 변환합니다.
2. 전역 변수로 min 변수를 선언하고 n으로 초기화 합니다. (전력망이 나누어 져 결과를 비교하였을 때 항상 버림 받는 값입니다. - 충분히 큰 값)
3. DFS 완전 탐색 알고리즘을 작성합니다.

더 이상 자식이 존재하지 않는 leaf 노드부터 탐사하기 위해서이며, 해당 방식을 leaf에 도달하였을 때 1을 반환합니다.
그리고 DFS 탐사에서 자식이 반환한 값을 본인의 값에 더해 자신의 값을 자기 자신과 그가 보유하고 있는 총 자식의 수를 얻을 수 있게 합니다.
그리고 모든 노드들에 대해서 값을 반환하기 전에 부모와의 연결을 끊었을 때를 가정하여 min의 값을 다시 계산하도록 합니다. (계산 방법은 현재의 min 값과 전체의 값에 node가 보유하고 있는 개수를 뺀 값(전체 - node 보유값은 반대편 전력망이 보유하고 있는 송전탑의 수 이다.)에 node가 보유하고 있는 값을 뺀 후 절대값을 씌운 값중에서 최소값을 구합니다)

글로는 복잡해 보일 수 있기에 코드를 통해 살펴 보겠습니다.

코드

import java.util.*;

class Solution {
    
    // 전역 변수 최소값
    int min;
   
    public int solution(int n, int[][] wires) {
   		// 적당히 큰 수로 초기화하여 전력망을 나누었을 때 바로 초기값이 변화하도록 설정     
        min = n;
        
        // wires 배열을 graph 형식으로 만들기 위한 Map 
        Map<Integer, List<Integer>> map = new HashMap<>();
        
        // map 초기화 작업
        for (int i = 1; i <= n; i++) {
            map.put(i, new ArrayList<>());
        }
        
        // 간선에 대한 정보를 바탕으로 서로에 대한 연결 내용을 양쪽에 저장
        for (int[] wire : wires) {
            map.get(wire[0]).add(wire[1]);
            map.get(wire[1]).add(wire[0]);
        }
        
        // 노드를 방문했는 지에 대한 여부를 체크하기 위한 배열
        boolean[] visited = new boolean[n+1];
        
        // DFS 함수 실행
        dfs(map, visited, 1, n);
        
        // 함수내에서 정해진 min의 값을 반환
        return min;
    }
    
    // DFS 함수
    int dfs(Map<Integer, List<Integer>> map, boolean[] visited, int start, int n) {
        // 현재 출발하는 노드 방문 설정
        visited[start] = true;
        
        // 현재 노드의 수를 계산
        int count = 1;
        
        // 현재 노드가 보유하고 있는 자식의 배열을 구함
        List<Integer> nexts = map.get(start);
        
        // 자식을 돌면서 자식들의 반환하는 노드의 수를 재귀적으로 더함
        for(int next : nexts) {
            if (!visited[next]) {
                count += dfs(map, visited, next, n);
            }
        }
        
        // 현재의 min값과 현재 노드를 기준으로 나눈 min 값의 차이중 더 작은 값을 min으로 설정
        min = Math.min(min, Math.abs(n - 2 * count));
        
        // 현재 노드가 포함하는 자식과 본인의 수를 반환
        return count;
    }
    
}