[JS] 전력망을 둘로 나누기

완전탐색 & DFS를 활용해서 구현해보았다.

 

 

1. 우선 각 노드의 간선을 저장해둔 tree를 만들어둔다. 

( 이때 양쪽 둘다 연결된 간선이라고 생각한다.)

2. 선을 하나씩 끊어보면서 개수를 직접 센다 (완전탐색)

3. 개수를 세는 과정은 스택을 활용한 bfs로 구현하였다.

4. 각 개수들을 세가면서 최소의 값을 갱신하면서 저장한다.

 

 

 

function solution(n, wires) {
    const tree = [...new Array(n+1)].map(_ => [])
    
    for (const [s,e] of wires){
        tree[s].push(e)
        tree[e].push(s)
    }
    
    let ret = n
    for (const [s,e] of wires) {
        const tmpTree = tree.map((el,idx) => {
            if (idx===s && el.includes(e)) return el.filter(el=>el!==e)
            if (idx===e && el.includes(s)) return el.filter(el=>el!==s)
            return el
        })
        const visited = [...new Array(n+1)].fill(false)
        const stk = []
        const cnt = []
        for (let i = 1 ; i <= n ; i ++){
            if (visited[i]) continue
            visited[i] = true
            stk.push(...tmpTree[i])
            let curCnt = 1
            while(stk.length) {
                const node = stk.pop()
                if (visited[node]) continue
                visited[node] = true
                stk.push(...tmpTree[node])
                curCnt++
            }
            cnt.push(curCnt)
        }
        const num = Math.abs(cnt[0]-cnt[1])
        ret = Math.min(num,ret)
    }
    
    return ret
}

 

 

 

나 자신한테 피드백을 주자면 굳이 tree로 tmpTree를 만들것이 아니라, 하나씩 제외해나가면서 tree를 그때그때 만들었어도 될 것 같다.

 

그리고 해당 문제는 무조건 나누어지는게 2팀이기 때문에 1번 노드의 개수만 구해도 반대편 노드의 개수를 구할 수 있었다..

 

(아님 차라리 유니온 파인드 쓰는것도 괜찮았을 것 같다)