[프로그래머스] 전력망을 둘로 나누기 풀이 / JavaScript

프로그래머스

 

작성 코드 (1차 시도 / 통과)

function solution(n, wires) {
    const graph = Array.from({length: n + 1}, () => Array(n + 1).fill(0))
    const dfs = (arr, node) => {
        let res = 0
        for (let i = 1; i <= arr[node].length; i += 1) {
            if (arr[node][i]) { // 연결되어 있다면 방문 처리
                arr[node][i] = arr[i][node] = 0
                res += 1 + dfs(arr, i)
            } 
        }
        return res
    }
    let result = 100
    
    // 와이어 연결 정보 저장
    wires.forEach(wire => {
        graph[wire[0]][wire[1]] = graph[wire[1]][wire[0]] = 1
    })
    // 와이어를 하나씩 끊고 끊어진 각 노드 2개에 대하여 DFS수행 후의 차이를 계산
    wires.forEach(wire => {
        const copy = graph.map(v => v.slice());
        const [a, b] = wire
        copy[a][b] = copy[b][a] = 0
        result = Math.min(result, Math.abs(dfs(copy, a) - dfs(copy, b)))
    })
    return result
}

구현 로직 (DFS)

기막힌 방법이 생각나지 않는다면 모든 케이스의 경우를 계산해보는 것이 차라리 깔끔합니다. 와이어를 하나씩 끊어보며 DFS를 수행해봅니다.

 

1. 와이어 연결 정보를 담을 graph 초기화

2. 와이어 연결 정보 저장

3. wires를 순회하며 현재 들어온 wire를 끊고난 후의 graph를 끊어진 각 노드에 대하여 DFS 수행.

4. 수행 후 결괏값의 차이와 이전에 수행했던 값 중 더 작은 값을 저장