프로그래머스 [Lv. 2] 전력망을 둘로 나누기 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(n, wires) {
    let answer = 101;
    const adjL = Array(n+1).fill().map(() => [])
    wires.forEach(([s, e]) => {
        adjL[s].push(e);
        adjL[e].push(s);
    })
    const bfs = (s, e) => {
        let V = Array(n+1).fill().map((e) => 0);
        let cnt = 1;
        const q = [1];
        V[1] = 1;
        while (q.length > 0) {
            const start = q.shift();
            for (const next of adjL[start]) {
                if (V[next] !== 0 || (s === start && e === next) || (e === start && s === next)) {
                    continue
                }
                V[next] = 1;
                cnt += 1;
                q.push(next)
            }
        }
        return cnt * 2;
    }
    
    wires.forEach(([s, e]) => {
        answer = Math.min(Math.abs(n - bfs(s, e)), answer)
    })
    return answer;
}

풀이 방법

1. adjL을 구성한다.
2. bfs를 만들고 1번 부터 순회할 수 있도록 한다.
   1. 현재 s, e 또는 e, s가 자르려고 하는 전선이므로 start와 next가 일치하는지 비교한다.
      1. 이 과정에서 파이썬은 (e, s) == (start, next)와 같이 비교하지만 자바스크립트는 그럴 수 없었다.
   2. cnt * 2를 return한다.
      1. 현재 이동한 송전탑의 개수 = cnt
      2. 이동하지 않은 송전탑의 개수 = n - cnt
      3. 전력망을 둘 로 나눈 후 송전탑의 차이 = | n - cnt * 2 |
3. answer와 비교해서 최소값을 출력한다.

느낀점

• 우선 이걸 참고하면 좋다 https://sound-programming.tistory.com/161
• 빈 배열 만드는 것이 익숙하지 않아서 오래 걸린 문제였다.
• 추가로 배열 비교는 아래를 참고하면 좋다.
• https://sound-programming.tistory.com/163

자바스크립트 [배열 비교]

자바스크립트 [빈 배열을 요소로 가진 배열 만들기]