전력망을 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

주석은 나중에 추가 예정..

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        
        Map<Integer, Tower> towers = new HashMap();
        
        for (int i = 0; i < wires.length; i++) {
            
            int v1 = wires[i][0];
            int v2 = wires[i][1];
            
            Tower t1 = towers.computeIfAbsent(v1, (key) -> Tower.of(v1));
            Tower t2 = towers.computeIfAbsent(v2, (key) -> Tower.of(v2));
            
            t1.connect(t2);
                        
        }
        
        int diff = 100;
        
        for (int i = 0; i < wires.length; i++) {
            
            int v1 = wires[i][0];
            int v2 = wires[i][1];
            
            Tower t1 = towers.get(v1);
            Tower t2 = towers.get(v2);
            
            t1.disconnect(t2.num);
            
            int cnt;
            
            Set<Integer> c = t1.connected(t1.num);
            
            diff = Math.min(diff, Math.abs(c.size() - (n - c.size())));
            
            t1.connect(t2);
            
        }
        
        return diff;
    }
    
    static class Tower {
        int num;
        Map<Integer, Tower> connectedMap = new HashMap();
        
        static Tower of (int num) {
            Tower vo = new Tower();
            vo.num = num;
            return vo;
        }
        
        void connect(Tower target) {
            connectedMap.put(target.num, target);
            target.connectedMap.put(this.num, this);
        }
        
        void disconnect(int num) {
            Tower target = connectedMap.remove(num);
            target.connectedMap.remove(this.num);
        }
        
        Set<Integer> connected(int parent) {
            Set<Integer> s = new HashSet();
            s.add(this.num);
            for (Tower t : connectedMap.values()) {
                if (t.num == parent) continue;
                
                Set<Integer> connected = t.connected(this.num);
                for (int c : connected) {
                    s.add(c);
                }
            }
            return s;
        }
        
    }
}