[union find, dfs] 전력망을 둘로 나누기

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

 

 

 

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1

=> 완전탐색. 각 전선을 하나씩 끊어 보며 모두 탐색가능

 

첫번째 풀이 (성공) - 유니온 파인드

• wires를 순회하며 앞에서부터 전선을 하나씩 끊는다
• 끊은 상황마다 union find를 통해 연결된 송신탑들의 부모를 통합한다
• 통합 뒤에 각 부모마다 송신탑개수를 구한다
• 그 중 최소, 최대 차이의 절대값을 구하고 이전의 answer과 비교한다

splice주의
splice는 원래 배열을 변경하고,  자르고 남은 부분을 리턴한다

const newArr = [...arr].splice() //가 아니라

const newArr = [...arr] // 먼저 복사하고 
newArr.splice(); // splice

 

유니온 파인드 주의
a, b의 부모를 둘 중 작은거로  통합할 때, 큰 걸 부모로 갖고 있는 다른 애들도 새로운 부모로 통합해줘야 한다 

 

function find(n, parents) {
    // 자기자신이 부모
    if (n = parents[n]) return n;
    return find(parents[n], parents)
}
    
function union(a, b, parents) {
    a = find(a, parents);
    b = find(b, parents);
    
    if (a <= b) parents[b] = a;
    else parents[a] = b;
}

function solution(n, wires) {
    var answer = -1;
    const obj = {};
    // 완전탐색 모든 선을 끊어보고 가장 작은 차이를 리턴
    for (let i = 0; i < wires.length; i++) {
        const parents = Array.from({length: n+1}, (_, i) => i); // 자기자신을 parent로
        const newWires = [...wires];
        newWires.splice(i, 1); // i번째 제외하고 나머지 선들
        // 나머지 선들의 전력망을 확인
        for (const [from, to] of newWires) {
            // 둘을 이어준다
            union(from, to, parents);        
        }
        // 각 전력망마다 송전탑개수 구하기
        const countObj = {};
        for (let i =1; i < parents.length; i++) {
            countObj[parents[i]] = (countObj[parents[i]] || 0) + 1; 
        }
        // 최대-최소
        const counts = Object.values(countObj);
        const diff = Math.abs(counts[0]-counts[1]);
        if (answer < 0) {
            answer = diff;
        } else {
            answer = Math.min(answer, diff);
        }
    }
    return answer;
}

 

 

두번째 풀이 (성공) - dfs

첫번째와 마찬가지로 하나씩 끊은 다음 dfs를 통해 최대, 최소 송전탑 개수를 구한다.