⚡

전력망을 둘로 나누기

레벨

LV.2

날짜

Oct 6, 2023

링크

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

🔎 문제

school.programmers.co.kr

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

🧩 구현과정 및 코드

개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.

사용할 데이터 구조와 풀이 방향성

적용할 알고리즘 혹은 메서드

수영

구현

그래프 DFS

인접행렬

코드

정은

구현

(처음 방식) wires를 돌면서 해당 연결을 끊었을 때 노드 수의 차이를 구해보려 했었다. ⇒ 구현하는게 은근 쉽지 않았던.. 다시 시도 예정 (다른 풀이) bfs로 진행. 한 원소를 제거하여 연결 끊음 ⇒ 사실 연결이 아닌 노드를 삭제한다는게 잘 이해가 안되는데, 다시 한번 볼 예정

코드

종혁

구현

전선 하나를 끊는다는 의미는 wires 배열에 있는 원소 하나를 무시한다는 의미로 받아드림

wires 전체를 이용해서 그래프를 만들고 , 각 원소의 연결를 그래프에서 제거해줌

이 때 노드끼리의 연결상태가 어떻게 되는지를 조사

코드

재웅

구현

간선을 잘라, 두 그룹의 노드 갯수 차이가 최소가 되는 경우

정확히 따지면 그래프 하위 구조인 트리 구조이기 때문에, 간선을 자르면 무조건 2등분됨

모든 경우를 끊어보며 최소가 되는 경우를 찾음 -> DFS

인접리스트 생성 이후 막혀 해설을 보고 분석하는 방식으로 진행하였습니다.

코드

✏️ 후기

문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.

👧🏻

수영

최대 안전 정수를 처음 알게 됐다!

👧🏻

정은

많은 문제를 풀어서 코드 구현의 능숙도를 향상시켜야겠다.

👦🏻

종혁

유니온파인드 알고리즘을 공부해봐야겠다

👦🏻

재웅

역대급 난이도에 전의를 상실했습니다……

유니온-파인드 알고리즘을 새로 알게 되었는데, 이를 적용하여 문제를 풀어보려 합니다.


// DFS, 그래프, 인접행렬
function solution(n, wires) {
    // 최대 안전 정수
    let answer = Number.MAX_SAFE_INTEGER;
    let count = 1;
    const visited = Array.from({length: n + 1}, () => false);
    const graph = Array.from({length: n + 1}, () => Array(n + 1).fill(0));
    
    for(const [v1, v2] of wires) {
        graph[v1][v2] = 1;
        graph[v2][v1] = 1;
    }
    
    function DFS(L){
        for (let i = 1; i <= n; i++) {
            if(visited[i] === false && graph[L][i] === 1) {
                visited[L] = true;
                count++;
                DFS(i);
                visited[L] = false;
            }
        }
    }
    
    for (let [v1, v2] of wires) {
        graph[v1][v2] = 0;
        graph[v2][v1] = 0;
        count = 1;
        DFS(1);
        graph[v1][v2] = 1;
        graph[v2][v1] = 1;
        answer = Math.min(answer, Math.abs(n - count - count));
    }
    return answer;
}


function solution(n, wires) {
    var answer = Infinity; 
    let connection = [{}];
    
    for (const wire of wires) {
        const [v1,v2] = wire;
        
        if (!connection[v1]) {
            connection[v1] = {};
        }
        if (!connection[v2]) {
            connection[v2] = {};
        }
        connection[v1][v2]=1;
        connection[v2][v1]=1;
    }
    
    for (const wire of wires) {
        const [v1,v2] = wire;
        const tree1 = new Set([v1]);
        let connectionCopy = connection;
    
        delete connectionCopy[v1].v2;
        delete connectionCopy[v2].v1;
       
        
        while (true) {
            const prevTreeSize = tree1.size;
            
            for(const leaf of tree1) {
                tree1.add(Object.keys(connectionCopy[leaf]));
                connectionCopy[leaf] = {};
            }
            
            if (tree1.size === prevTreeSize) {
                answer = Math.min(answer, tree1.size);
                break;
            }
        }
    }
    
    
    return answer;
}


function deepCopy(arr) {
  return arr.map(subArr => [...subArr]);
}//이중배열의 deep copy
function solution(n, wires) {
    const graph = Array.from({length : n+1},() => [])
    wires.forEach(([start,next]) => {
        graph[start].push(next)
        graph[next].push(start)
    })
   //하나를 끊는다 - wires 배열에 있는 원소 하나를 안쓰겠다는 소리
    let difference = Infinity
    wires.forEach(([start,next]) => {
        const copy = deepCopy(graph)
        //graph를 deep copy한 배열에 start-next 연결된걸 제거
        copy[start].splice(copy[start].indexOf(next),1)
        copy[next].splice(copy[next].indexOf(start),1)
        const isUsed = Array(n+1).fill(0)
        const divide = []
        for(let i=1;i<=n;i++){//전체 노드의 연결상태 조사
            if(isUsed[i]){continue}//기존에 연결되어있는걸 확인한 노드는 다시 조사 X
            isUsed[i] = 1
            divide.push(checkConnection(i,isUsed,copy))
        }
            //예시 1번) wires의 각 원소를 끊었을 때 분리된 전력망들이 가지고 있는 송전탑 개수 (+1해서 생각)
        	// [ 0, 7 ]
        	// [ 7, 0 ]
        	// [ 2, 5 ] - 절댓값 제일 작음
        	// [ 7, 0 ]
        	// [ 7, 0 ]
        	// [ 5, 2 ] - 절댓값 제일 작음
        	// [ 7, 0 ]
        	// [ 7, 0 ]
        if(divide.length === 2){//문제에서 두 전력망으로 나누었을때만 고려하라고 했음
            difference = Math.min(difference,Math.abs(divide[0] - divide[1]))
        }
        if(difference === 0){return 0}
    })

		const checkConnection = (indexNode,isUsed,copy) => {//indexNode와 연결되어있는 노드가 몇개가 있는지 조사
        let count = 0 
        const queue = [indexNode]
        while(queue.length){//index 노드부터 시작해서 - 연결되어있는 노드를 bfs 방식으로 찾기
            const curNode = queue.shift()
            for(const nextNode of copy[curNode]){
                if(isUsed[nextNode]){continue}
                queue.push(nextNode)
                isUsed[nextNode] = 1
                 count++
            }
        }
        return count+1 // indexNode와 연결되어있는 노드의 수
    }
    return difference
}


function solution(n, wires) {
    const links = {}; 

// 인접리스트 생성
    wires.map(w => {
        const [a, b] = w;
        if(!links[a]) links[a] = [];
        if(!links[b]) links[b] = [];
        links[a].push(b);
        links[b].push(a);
    })
    
// exception을 제외한 연결 노드 수를 계산하는 함수
// DFS를 이용, 노드 간 방문처리
    const searchTree = (root, exception) => {
        let count = 0;
        const queue = [root];
        const visited = [];

        visited[root] = true;
        while(queue.length){
            const cur = queue.pop();
            links[cur].map(next => {
                if(next !== exception && !visited[next]){
                    visited[next] = true;
                    queue.push(next);
                }
            })
            count++;
        }
        return count;
    }
    
// 나올 수 있는 최대값 N-2
// wires를 순회하여 연결을 끊음
    let answer = n-2; 
    wires.map((w, i) => {
        const [a, b] = w;
        const dif = Math.abs(searchTree(a,b) - searchTree(b,a));
        answer = answer > dif ? dif : answer;
    })
    return answer;
}