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

문제

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

프로그래머스

 

---

문제 풀이

해당 문제는 송전탑의 연결 상태를 파악한 후 모든 전선을 한번씩 잘라보며 각 전원의 송전탑의 수의 차이를 구하는 문제이다.

 

문제를 풀 때 송전탑의 연결을 송전탑의 오브젝트에 넣어두어 연결 상태를 확보한 후 끊긴 이 후 송전탑의 수를 구했다.

 

글보다 코드를 보면 이해가 쉬울 것 같다.

function countLink (link,start) {
    let answer = 0;
    const queue = [start];
    const list = [start];
    
    while(queue.length){
        const target = queue.shift();
        link[target].forEach((x)=>{
            if(list.includes(x))    return;
            list.push(x);
            queue.push(x);
        })
    }
    return list.length;
}


function solution(n, wires) {
    var answer = n;
    const link = {};
    wires.forEach(([a,b])=>{
        if(link[a])     link[a].push(b);
        else            link[a] = [b];
        
        if(link[b])     link[b].push(a);
        else            link[b] = [a];
    })
    
    wires.forEach(([a,b])=>{
        const tempLink = {...link};
        tempLink[a] = tempLink[a].filter((x)=>x!==b);
        tempLink[b] = tempLink[b].filter((x)=>x!==a);
        
        const result = Math.abs(countLink(tempLink,a) - countLink(tempLink,b));
        if(answer > result) answer = result;        
    })
    return answer;
}