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

전력망을 둘로 나누기

문제 링크

전력망을 둘로 나누기

분석

송전탑들이 연결된 트리가 주어졌을 때, 특정 간선 하나를 제거하여 두 개의 전력망으로 나누고, 개수 차이가 가장 적은 최소값을 반환하는 문제입니다.

트리 구조로 주어지며, 실제 트리가 주어지진 않습니다.
주어진 트리 구조는 양방향으로, 사이클이 없고, 가중치가 없는 그래프라고 볼 수 있습니다.
이 문제에서는 인접 리스트가 가장 효율적입니다.

트리 구조이므로, 간선 하나를 제거하면 반드시 두 개의 부분 그래프가 생성됩니다.

DFS와 BFS를 사용해서 문제를 풀 수 있습니다.

즉, 그래프를 사용하여 각 간선을 하나씩 제거해보면서 DFS혹은 BFS로 탐색하여 크기를 비교해본 후, 차이의 최소값을 구하는 방식으로 해결할 수 있습니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

// dfs로 연결된 송전탑 개수 계산
int dfs(int node)
{
    // 방문 처리
    visited[node] = true;
    // 현재 노드 포함해서 개수를 센다.
    int count = 1;
    
    // 반복문으로 방문 가능한 노드를 방문해서 개수를 센다.
    for (int next : graph[node])
    {
        if (visited[next] == false)
        {
            count += dfs(next);
        }
    }
    
    return count;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = n;

    // 그래프 초기화
    graph.assign(n + 1, vector<int>());
    for (auto& wire : wires)
    {
        int a = wire[0], b = wire[1];
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    // 모든 간선을 제거해보면서 최소값을 찾는 반복문
    for (auto &wire : wires)
    {
        int a = wire[0], b = wire[1];
        
        // 간선을 제거합니다
        // wire[0]에서 wire[1]로 이어져있는 간선, wire[1]에서 wire[0]으로 이어져있는 간선
        graph[a].erase(remove(graph[a].begin(), graph[a].end(), b), graph[a].end());
        graph[b].erase(remove(graph[b].begin(), graph[b].end(), a), graph[b].end());
        
        // visited를 false로 초기화
        visited.assign(n + 1, false);
        // 제거된 간선에서 한쪽 서브트리의 크기를 구합니다.
        int subTreeSize = dfs(a);
        //다른 서브트리의 크기를 구합니다.
        int otherTreeSize = n - subTreeSize;
        
        // 최소 차이를 비교하고 갱신합니다.
        answer = min(answer, abs(subTreeSize - otherTreeSize));
        
        // 간선을 복구합니다.
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n^2)$입니다.

• 그래프 초기화 graph.assign(n + 1, vector<int>()) $O(n)$
• 그래프 초기화하는 반복문 $O(n)$
• 간선을 제거해보면서 최소값을 찾는 반복문 $O(n^2)$
• $O(n + n + n^2)$

공간 복잡도는 $O(n)$입니다.

• 그래프를 저장하는 vector<vector<int>> graph $O(n)$
• 방문했는지 저장하는 vector<bool> visited $O(n)$
• 재귀 호출 스택 $O(n)$
• $O(n + n + n)$

테스트 1 〉 통과 (0.05ms, 4.14MB)
테스트 2 〉 통과 (0.09ms, 3.68MB)
테스트 3 〉 통과 (0.10ms, 4.16MB)
테스트 4 〉 통과 (0.09ms, 3.66MB)
테스트 5 〉 통과 (0.10ms, 4.14MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.23MB)
테스트 8 〉 통과 (0.01ms, 4.22MB)
테스트 9 〉 통과 (0.01ms, 4.16MB)
테스트 10 〉 통과 (0.07ms, 4.22MB)
테스트 11 〉 통과 (0.08ms, 3.74MB)
테스트 12 〉 통과 (0.11ms, 4.12MB)
테스트 13 〉 통과 (0.07ms, 3.68MB)