[프로그래머스][코딩테스트 고득점 Kit][Javascript] 전력망을 둘로 나누기

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

프로그래머스

 

function solution(n, wires) {
	// n이 100 이하이므로 answer 101로 초기화
	let answer = 101;
    
	// wires를 통해 tree 생성
	let tree = Array.from(Array(n+1),()=>[]);
    
	wires.map((element)=>{
		let [a,b] = element;
		tree[a].push(b);
		tree[b].push(a);
	})
	...
	return answer;
}

bfs 함수

// start : bfs 탐색 시작점
// except : 제외할 노드
function bfs(start, except){
    // 주어지는 배열 크기(n)와 같은 크기의 배열 선언 및 false로 초기화
    // 직관적 index 접근을 위해 n+1로 크기 초기화
    const visited = Array.from({ length: n+1 }, () => false);        
    let count =0;
    let queue = [start];
    visited[start]=true;

    while(queue.length){
        let index=queue.pop();
        tree[index].forEach((element)=>{
            // 방문하지 않은 노드이고
            // 제외할 노드가 아니면
            // 방문 가능
            if(element !== except && visited[element] == false){
                // 방문 완료 표시
                visited[element]=true;
                // 다음 방문을 위해 queue에 push
                queue.push(element);
            }
        })
        count++;
    }
    return count;
}

    // 모든 노드 간의 연결을 하나씩 제외해가면서 완전탐색
     wires.forEach(element => {
        let[a,b] = element;
        answer = Math.min(answer, Math.abs(bfs(a,b)-bfs(b,a)))
    });

ex) a=1, b=3인 경우 → 1번과 3번 전력망이 끊어진 경우
bfs(1,3) → 3을 제외하고 1과 연결된 전력망 개수 탐색
bfs(3,1) → 1을 제외하고 3과 연결된 전력망 개수 탐색

 

Math.abs( bfs(a,b) - bfs(b,a) )
→ 1번과 3번 전력망이 끊어진 경우에

두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)

---

전체코드

function solution(n, wires) {
    let answer = 101;
    let tree = Array.from(Array(n+1),()=>[]);
    wires.map((element)=>{
        let [a,b] = element;
        tree[a].push(b);
        tree[b].push(a);
    })
    
    function bfs(start, except){
        const visited = Array.from({ length: n+1 }, () => false);        
        let count =0;
        let queue = [start];
        visited[start]=true;

        while(queue.length){
            let index=queue.pop();
            tree[index].forEach((element)=>{
                if(element!==except&&visited[element]==false){
                    visited[element]=true;
                    queue.push(element);
                }
            })
            count++;
        }
        return count;
    }
     wires.forEach(element => {
        let[a,b] = element;
        answer = Math.min(answer, Math.abs(bfs(a,b)-bfs(b,a)))
    });
    return answer;
}