[C++] Programmers Lv. 2 "전력망을 둘로 나누기"

🔵 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

🔵 문제 접근

하나의 트리를 두 개로 나눈다.

이때, 두 트리의 노드 수 차이가 최소가 되도록 했을 때 그 최소 차이를 반환하는 문제이다. 

 

문제에서 n은 최대 100이므로 O(N^2)의 시간 복잡도로도 문제를 충분히 해결할 수 있겠다는 생각이 든다.

따라서 트리 간 이어진 간선을 하나씩 끊어보며 두 트리의 노드 수의 차이를 일일이 구하여 비교하는 방법을 택했다.

 

그래프를 인접 리스트로 표현 할 때, 간선을 끊는 방법을 메모하고자 한다. (문법 내용)

        // 간선 끊기
        graph[start].erase(remove(graph[start].begin(), graph[start].end(), end), graph[start].end());
        graph[end].erase(remove(graph[end].begin(), graph[end].end(), start), graph[end].end());

vector의 erase(it1, it2)는 이터레이터1부터 이터레이터2 바로 전까지의 원소들을 삭제한다.

즉, [it1, it2) 범위의 원소를 삭제시킨다.

 

algorithm 헤더의 remove(범위 시작, 범위 마지막, 삭제할 값)를 실행했을 때, remove는 실제로 원소를 삭제하지 않는다.

지우고 싶은 값들을 vector 뒤로 밀어내고 그 위치의 이터레이터를 반환한다.

 

따라서 remove로 삭제한 값을 graph[start] 맨 뒤로 밀어내고 그 위치를 반환하면, erase로 그 위치부터 end까지 원소를 삭제한다는 의미이다.

축약하자면 remove로 뒤로 밀려난 쓰레기값을 erase로 제거하는 것이다.

 

이 문제에서 위 구문이 시간 복잡도에 미치는 영향은 미미하다.

remove, erase 모두 시간 복잡도는 해당 노드의 연결 리스트 길이에 비례하는데, 노드 수가 n일 때, 간선 수가 n - 1이므로 노드의 평균 차수(간선 수)가 매우 작기 때문이다. 

따라서 상수 시간으로 봐도 무방하다. 

 

🔵 전체 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// n은 100 이하 wires는 최대 99
// 하나의 트리를 2개로 분할
// 이때 최대한 송전탑의 개수를 비슷하게 
// n이 작으므로 일일이 확인하면 됨

// dfs를 하며 노드 개수를 센다. 
int dfs(const vector<vector<int>>& graph, vector<bool>& visited, int start)
{
    visited[start] = true;
    int count = 1;

    for (int end : graph[start])
    {
        if (!visited[end])
            count += dfs(graph, visited, end);
    }

    return count;
}

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

    // 그래프 생성
    for (int i = 0; i < wires.size(); i++)
    {
        int start = wires[i][0] - 1;
        int end = wires[i][1] - 1;

        graph[start].push_back(end);
        graph[end].push_back(start);
    }

    // 선을 하나씩 잘라본다.
    for (int i = 0; i < wires.size(); i++)
    {
        vector<bool> visited(n, false);
        int start = wires[i][0] - 1;
        int end = wires[i][1] - 1;

        // 간선 끊기
        graph[start].erase(remove(graph[start].begin(), graph[start].end(), end), graph[start].end());
        graph[end].erase(remove(graph[end].begin(), graph[end].end(), start), graph[end].end());

        int ret1 = dfs(graph, visited, start);
        int ret2 = n - ret1;

        answer = min(abs(ret1 - ret2), answer);

	// 간선 복구
        graph[start].push_back(end);
        graph[end].push_back(start);
    }

    return answer;
}

 

🔵 시간 복잡도

노드 수를 N이라 하고, 간선 수를 N - 1이라 하자.

모든 간선을 반복하며 끊는 행위가 O(N - 1)이고 각 노드를 dfs로 탐색하는 것은 O(N)이 걸리므로, 총 시간 복잡도는 O(N^2)이다.