문제
코드
function solution(n, wires) {
const dict = {};
const answer = [];
for(let wire of wires){
if(!(wire[0] in dict))
dict[wire[0]] = [wire[1]];
else
dict[wire[0]].push(wire[1]);
if(!(wire[1] in dict))
dict[wire[1]] = [wire[0]];
else
dict[wire[1]].push(wire[0]);
}
for(let wire of wires){
const [start, end] = wire;
const stack = [...dict[start]];
const visited = {};
let count = 1;
visited[start] = true;
visited[end] = true;
while(stack.length !== 0){
const temp = stack.pop();
if(!visited[temp]){
visited[temp] = true;
stack.push(...dict[temp]);
count+=1;
}
}
answer.push(Math.abs(count*2-n));
}
return Math.min(...answer);
}
dictionary에 연결된 전선 배열 넣기
- Map이나 객체를 이용해 연결된 전선을 배열로 넣어요!
- 저는 객체가 편해서 객체로 고고
wires에서 하나씩 끊어보기
- wires에서 하나씩 끊는데
visited
를 사용하여 끊어진 부분의 시작과 끝을 visited 처리하여 끊어진 곳으로 넘어가지 못 하도록 하고, 시작점을 기준으로 연결된 선을 따라가요!
- 처음 stack에 들어간 시작점과 연결된 배열을 pop하며 temp에 넣어줘요!
- 방문하지 않은 곳들을 돌며 visited를 바꿔주고, 연결된 배열을 다시 stack에 넣어줘요!
주의!!! 꼭 spread 연산자로 넣어줘서 배열을 풀어줘야 합니다!
미친 계산법 Math.abs(n - count*2)
- 전체에서 카운트를 두 번 빼주는 이유는 남은 전선 두개의 차를 구해야하기 때문이에요.
- 전체 전선 = 8, count = 3라고 하면 남은 전선은 5개니까
8-3*2 = 2
정답이쥬?