99클럽 코테 스터디 10일차 TIL - 완전탐색

항해99 코테 스터디 10일차 문제인 프로그래머스의 '전력망을 둘로 나누기'는 트리 구조로 이루어진 전력망에서 전선 하나를 끊어 나누어진 두 트리의 노드 개수의 차의 최솟값을 구하는 문제다. 난이도는 레벨이며 완전탐색을 통해 해결할 수 있다.

 

오늘의 문제 - 전력망을 둘로 나누기 문제 정보

문제 키워드

- 브루트 포스 (완전탐색)

난이도

- Level 2

 

문제 요약

• 트리 구조로 이루어진 전력망이 주어진다. 노드의 개수는 n이며 엣지의 개수는 n-1개이다.
• 전선 하나를 끊어 전력망을 둘로 나누었을 때, 두 전력망의 노드의 개수의 차의 최솟값을 구하여라.

 

문제 풀이 과정  

• n의 범위가 100 이하이므로, 모든 전선을 끊어보며 결과값을 확인할 수 있다.
• 따라서 전선을 끊었을 때 두 전력망의 노드를 구하는 메소드를 구현하여, n-1번 끊어가며 최솟값을 구할 수 있다.
• 전력망의 노드의 개수를 구하는 메소드에서는 그래프 탐색 알고리즘 중 BFS를 이용하였다.
• 전력망이 트리 형태로 되어있으므로, 전선을 하나 끊었을 때 무조건 트리는 두개로 나누어진다. 따라서 한쪽의 노드 개수만 구하면 나머지 한쪽의 노드 개수도 구할 수 있다는 점을 이용하였다.

코드

import java.util.*;

class Solution {
    
    private List<List<Integer>> adjList = new ArrayList<>(); 
    
    public int solution(int n, int[][] wires) {
        
        // 인접 리스트 초기화 및 값 넣기
        for(int i=0; i<=n; i++) {
            adjList.add(new ArrayList<>());
        }
        for(int[] wire: wires) {
            int s = wire[0], d = wire[1];
            adjList.get(s).add(d);
            adjList.get(d).add(s);
        }
        
        // 와이어 하나씩 끊어보며 분할된 각 트리의 노드 개수를 구하고
        // 노드 개수 차의 절댓값 중 가장 작은 값으로 정답을 갱신
        int answer = Integer.MAX_VALUE;
        
        for(int[] wire: wires) {
            int nodeA = wire[0], nodeB = wire[1];
            int aCnt = getNodesCnt(n, nodeA, nodeB);
            int bCnt = n - aCnt;
            int abs = Integer.max(aCnt-bCnt, bCnt-aCnt);
            answer = Integer.min(answer, abs);
        }
        
        return answer;
    }
    
    // startNode가 포함된 트리의 노드의 개수를 구함
    // wirelessNode와는 끊어진 것으로 가정
    public int getNodesCnt(int n, int startNode, int wirelessNode) {
        int cnt = 0;
        
        boolean[] visited = new boolean[n+1];
        visited[startNode] = true;
        Queue<Integer> q = new LinkedList<>();
        q.add(startNode);
        
        while(!q.isEmpty()) {
            int hereN = q.poll();
            // 새로운 노드를 방문할 때마다 카운트 증가
            cnt++;
            
            // 현재 노드와 연결된 노드 중 방문하지 않은 노드 방문
            for(int nextN : adjList.get(hereN)) {
                // wirelessNode와는 끊어졌다고 가정하여 무시함
                if ((hereN == startNode && nextN == wirelessNode)
                    || (hereN == wirelessNode && nextN == startNode)) {
                    continue;
                }
                
                // 아직 방문하지 않은 노드 방문
                if (!visited[nextN]) {
                    visited[nextN] = true;
                    q.add(nextN);
                }
            }
        }
        
        return cnt;
    }
}

• 시간복잡도: O(N^2)
• 공간복잡도: O(N^2)

 

오늘의 학습 회고

새롭게 알게된 것

• 문제의 조건을 잘 확인하여, 불필요한 연산을 추가하지 않도록 유의해야겠다.
  • 이 문제에서는 트리이기 때문에 한 엣지를 끊으면 무조건 두개로 나누어지는데, 이를 생각하지 못하고 두 그룹의 노드를 각각 구하였다. 이 조건을 이용한다면 하나만 구한 뒤 전체 노드 개수에서 빼면 나머지 하나의 값을 빠르게 구할 수 있다.