[프로그래머스_완전탐색] 전력망을 둘로 나누기

프로그래머스

 

[문제 요구 사항]

- n개의 노드와 n-1개의 간선으로 이루어진 트리가 주어졌다. 이 때, 한 개의 간선을 끊었을 때 두 트리의 노드 차이를 최소한으로 하고 그 값을 구하여라

 

[문제 아이디어]

1. 모든 간선을 순회하며 하나씩 끊는다. 그리고 한 트리를 bfs를 돌리면 작은 트리의 노드 개수가 나온다. 이 때, bfs 개수 - (n-bfs 개수)가 최소가 되는 값을 찾는다.

- 시간 복잡도 예상 : 간선의 개수 * bfs worst case = (n-1) * (n-1) = n^2 

- 공간 복잡도 예상 : (방문체크 배열 길이 + queue의 최대 깊이) * 간선 개수(=반복 횟수) = 2n * (n-1) = n^2

 

2. 트리를 그리고 쌓아서 올라간다. 이를 DP로 표현하고 bfs 개수 - (n-bfs 개수)를 구해서 마지막에 가장 작은 값을 반환한다.

- 시간 복잡도 예상 : 일차 순회 = n

- 공간 복잡도 예상 : 순회 * 필요한 변수 개수(3-4) = 3n = n

 

2번으로 하고 싶은데, 규칙을 못 잡았다ㅣ. 리프노드를 1로 잡고 올렸는데 중간에 충돌하는 경우 규칙이 충돌해서 값이 이상해질 것으로 보였음. 그래서 1차 구현은 1번 아이디어로 진행

 

[1번 풀이 = 내 풀이]

function solution(n, wires) {
    let answer = 99999999
    
    const disconnectWire = (disconnectedWireNumber) => {
        return wires.filter((wire,i) => i !== disconnectedWireNumber)
    }
    
    const bfs = (changeWires) => {
        const visited = Array.from({length : n+1}, () => false)
        visited[1] = true
        const queue = [1]
        let cnt = 0

            
        while (queue.length > 0) {
            cnt += 1
            const node = queue.pop()
            for (let i =0; i< changeWires.length; i +=1) {
                if(changeWires[i][0] === node && visited[changeWires[i][1]] === false) {
                    visited[changeWires[i][1]]= true 
                    queue.push(changeWires[i][1])
                }
                
                if(changeWires[i][1] === node && visited[changeWires[i][0]] === false) {
                    visited[changeWires[i][0]] = true 
                    queue.push(changeWires[i][0])
                }
            }
        }
        
        return Math.abs(n- cnt *2)
    }
    
    for (let i =0; i<n; i+=1) {
        const value = bfs(disconnectWire(i))
        if (value < answer) {
            answer = value
        }
    }

    return answer;
}

- 간선을 순회하며 끊어진 간선 배열을 만들고 이를 전달하여서 bfs를 돌림.

풀이 결과 : 답은 맞으나 . 좀 느리다.

 

[2번 풀이 = 프로그래머스 딴 분 풀이]

function solution(n, wires) {
    let ans = 99999999

    // graph 생성
    const graph = Array.from({length : n}, () => [])
    for (const edge of wires) {
        graph[edge[0]-1].push(edge[1]-1) 
        graph[edge[1]-1].push(edge[0]-1) 
    }
    

    // Tree 형태로 변환
    const parents = new Array(n).fill(-1)
    const queue = [0]

    for (let i=0; i<queue.length; i++){
        const u = queue[i]
        for (const v of graph[u]) if (v != parents[u]) {
            parents[v] = u
            queue.push(v)
        }
    }

    // Tree 기반 간선 계산
    const dp = new Array(n).fill(1)
    for (let i = queue.length; i>0; i--){
        const v = queue[i]
        dp[parents[v]] += dp[v]

        const minValue = Math.abs(n-2*dp[v]);
        if (ans > minValue) ans = minValue
    }

    console.log(graph, parents, ans)


    return ans;
}

- 다른 분의 풀이인데, 약어를 많이 쓰셔서 변수명만 이해하기 쉽게 바꾸었다.

- 아이디어는 동일한데 나는 graph로 생각해서 dp를 제대로 적용하지 못했다. 하지만, 이 분은 이를 부모-자식 관계로 정리하여서 순서를 만들었고 이를 통해서 dp를 생성할 수 있었다. 마지막 자식부터 부모로부터 dp를 생성하니 내 생각과 동일하게 할 수 있었다.

압도적으로 빨라졌다

 

[고쳐야할 점]

- 오랜만에 풀어서 좀 많이 느렸다. 6배 정도 빨라져야한다.

- 코테 떨어진 적이 많은데 1번과 2번 차이 아닐까 싶다. 푸는 게 중요한 게 아니라 잘 푸는 것이 중요하다.