Algorithm
[프로그래머스][코딩테스트 고득점 Kit][Javascript] 전력망을 둘로 나누기
밍맹030
2023. 8. 7. 18:30
728x90
https://school.programmers.co.kr/learn/courses/30/lessons/86971
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
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;
}
728x90