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

     

목차

 

문제

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

프로그래머스

 

 

코드 구현 방향

모두의 경우에 대해 union Find로 만들어 본 뒤 부모들을 map에 넣어 길이가 2일 경우에만 조사하는 식으로 구현했다.

 

 

코드 구현

function find(a, parent){
    if(parent[a] === a) return a;
    return (parent[a] = find(parent[a], parent));
}

function union(a, b, parent, rank){
    let A = find(a, parent);
    let B = find(b, parent);
    
    if(A === B)return;
    if(rank[A] < rank[B]) parent[A] = B;
    else if(rank[A] > rank[B]) parent[B] = A;
    else {
        parent[A] = B;
        rank[B]++;
    }
}

function solution(n, wires) {
    var answer = wires.length;

    for(let i=0; i< wires.length; i++){
        let parent = Array.from({length: 101},(_, idx)=>idx);
        let rank = Array(101).fill(0);
        let m = new Map();
        for(let j=0; j< wires.length; j++){
            if(i !== j){
                union(wires[j][0], wires[j][1], parent, rank);
            }
        }
        for(let p=1; p<=n; p++){
            m.set(find(p,parent), (m.get(find(p, parent)) || 0) +1 );
        }
        
        if(m.size === 2){
            let cnt = 0;
            for(let [key, value] of m){
            //뺄셈을 하기 위해서는 교차로
                if(cnt === 0) cnt += value;
                else cnt -= value;
            }
            //차이는 양수
            answer = Math.min(answer, Math.abs(cnt));
        }
    }

    return answer;
}