[Javascript] 프로그래머스 - 전력망을 둘로 나누기

🧾 목차

1. 문제 설명

2. 문제 풀이

3. 전체 코드 (dfs)

4. 다른 풀이 (bfs)

---

1. 문제 설명

• n개의 송전탑이 트리 형태로 연결되어 있음.
• 주어진 전선들 중 하나를 끊어서 트리를 두 개의 전력망으로 분할해야 함.
• 두 전력망의 송전탑 개수 차이(절대값)를 최소화하는 경우를 찾아야 함.
• 이 최소 차이를 return 하는 함수를 구현해야 함.

---

2. 문제 풀이

트리에서 한 곳의 연결을 끊으면 2개로 나눠진다.

만약 [a, b] 를 끊었다면 a, b 노드는 각각 다른 트리에 속한다.

따라서 a에서 시작하는 dfs 순회를 돌려서 트리에 속한 노드 개수를 구하고, 2n 에서 개수를 빼서 절댓값을 구하면 된다.

 

1️⃣ 연결 초기화

 

2️⃣ dfs 함수

[a, b] 연결을 끊어서 a 부터 dfs를 돌린다면 exceptV는 b로 설정한다.

이 때 count를 1씩 증가시켜, 방문한 노드수를 누적 계산한다.

 

3️⃣ dfs 호출하는 부분

a부터 시작하는 dfs에서 거친 노드의 수를 cnt에 저장한다.

이때, 하나의 트리의 노드수가 cnt라면? 다른 트리의 노드수는 n - cnt이다.

두 값 차이의 절댓값이 정답이 된다.

 

⏰ 시간복잡도

cf) 그래프의 일반적인 표현 방식
- n : 노드(정점, vertices)의 개수
- e : 간선(edges)의 개수

 

dfs 순회 : O(n + e)

wire 순회 :  O(n-1) ≃ O(n)

👉 O(n(n+e)) , 이 때 트리의 e는 n - 1이다.

👉 O(2n^2) 

👉 O(n^2)

---

3. 전체 코드

function solution(n, wires) {
    var answer = Infinity;
    
    tree = Array.from({length: n + 1}, (v)=> []);
    
    for (const [from, to] of wires) {
        tree[from].push(to);
        tree[to].push(from);
    }
    
    
    for (const [from, to] of wires) { 
        var visited = Array.from({length: n + 1}, (v)=> false);
        var cnt = dfs(from, visited, to); 
        
        answer = Math.min(Math.abs(cnt - (n - cnt)), answer);
    }
   
    function dfs(v, visited, exceptV) {
        var count = 1;
        visited[v] = true;
        
        for (const nextV of tree[v]) {
            if (!visited[nextV] && nextV != exceptV) {
                count += dfs(nextV, visited, exceptV);
            }
        }
        
        return count;
    }
    
    return answer;
}

 

4. 다른 풀이

얼핏보면 bfs 처럼 보이지만, shift 연산 대신 pop을 한다는 점에서 bfs는 아니고, 어설픈 dfs 코드이다.

 

- 자바스크립트 코드는 bfs 를 구현하기에 좀 까다롭다. 왜냐면 직접 queue를 구현해야하기에..

- 하지만 최소 거리를 구해야하는 문제가 아닌, 

- 연결된 노드를 방문해야하는 문제는 어설픈 dfs 코드를 사용해도 괜찮다.

function solution(n, wires) {
    var answer = Infinity;
    
    tree = Array.from({length: n + 1}, (v)=> []);
    
    for (const [from, to] of wires) {
        tree[from].push(to);
        tree[to].push(from);
    }
    
    
    for (const [from, to] of wires) { 
        var cnt = searchTree(from, to); 
        
        answer = Math.min(Math.abs(cnt - (n - cnt)), answer);
    }
   
    function searchTree(v, exceptV) {
        var q = [v];
        var visited = Array.from({length: n + 1}, (v)=> false);
        var count = 0;
        visited[v] = true;
        
        while (q.length) {
            var cur = q.pop();
            count++;
            
            for (const next of tree[cur]) {
                if (!visited[next] && next != exceptV) {
                    visited[next] = true;
                    q.push(next);
                }
            }
        }
        
        return count;
    }
    
    return answer;
}

 

결론 

 

• n이 크면(n > 10^5)
  • DFS는 재귀 호출 스택이 깊어지면 스택 오버플로우 위험 있음 → BFS가 유리!
  • 트리 깊이가 작다면 DFS도 큰 문제 없이 작동할 수 있음.
• 메모리 효율은 DFS와 BFS가 거의 비슷하지만, BFS는 큐를 사용하므로 다소 더 메모리를 소모할 수도 있음.
• 전반적으로 BFS(searchTree)가 더 안전하고, 큰 n에서도 동작할 가능성이 높음.

👉 결론적으로, n이 매우크면 BFS(searchTree) 코드가 더 안전함!