[완전탐색 & 트리] 프로그래머스 '전력망을 둘로 나누기' - js

1. 문제

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

프로그래머스

2. 설명

푼 사람도 적은 정말 사악한 문제.. 나는 문제 보자마자 아 이건 알고리즘 개념을 알아야 풀 수 있겠다 싶어 구글링한 후 학습했다.

이 문제의 핵심은 n이 100까지라는 것이다 -> 종류가 적다?! -> 무조건 완탐으로 간다!!!!

+ '트리'가 나오면 방문한 노드를 체크하기 위해 큐를 써주는 것 같다. 큐를 사용할 때 중요한건?! 방문 여부 체크!! 방문 여부 체크를 안하면 무한루프에 빠진다. 주의하자ㅠㅠ

1. wires를 탐색하며 객체를 통해 연결된 모든 edge를 저장해준다.
2. 큐를 사용하여(방문한 노드 체크를 위해) 모든 연결된 노드를 방문하며 edge의 갯수를 센다(count).
3. 하나의 edge를 삭제한 후 edge의 갯수를 비교하여 차이가 최소값을 return 한다.

function solution(n, wires) {
    // wires 배열을 탐색하며 노드간 연결관계 객체로 저장
    // 루트 노드,제외할 특정 노드를 파라미터로 갖고 노드 별 간선 갯수 리턴하는 함수 작성
    // wires 배열 탐색하며 한 개의 연결 끊고 위에서 만든 함수에 
    // 각각 루트노드, 제외노드로 번갈아가며 넣어 결과의 차가 가장 적은 경우 리턴
    let answer = 0;
    let tree = {};
    wires.map((el) => {
        if(!(el[0] in tree)) tree[el[0]] = [];
        if(!(el[1] in tree)) tree[el[1]] = [];
        tree[el[0]].push(el[1]);
        tree[el[1]].push(el[0]);
    });
    
    const edge = (root, except) => {
        let count = 0;
        let queue = [root];
        let visited = [];
        visited[root] = true;
        
        while(queue.length > 0){
            let cur = queue.pop();
            tree[cur].map((el) => {
                if(el!==except && !visited[el]) {
                    queue.push(el);
                    visited[el] = true;
                }
            })
            count++;
        }
        
        return count;
    }
    
    answer = 100;
    
    wires.map((el) => {
        let temp = Math.abs(edge(el[0],el[1]) - edge(el[1],el[0]));
        if(answer > temp) answer = temp;
    })
    
    return answer;
}

 

복기

4/13