🔵 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/86971
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
🔵 문제 접근
하나의 트리를 두 개로 나눈다.
이때, 두 트리의 노드 수 차이가 최소가 되도록 했을 때 그 최소 차이를 반환하는 문제이다.
문제에서 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)이다.
'PS' 카테고리의 다른 글
| [C++] Programmers Lv. 2 "양궁대회" (0) | 2025.07.03 |
|---|---|
| [C++] Programmers Lv. 2 "피로도" (0) | 2025.07.02 |
| [C++] Programmers Lv. 3 "경주로 건설" (0) | 2025.06.24 |
| [C++] Programmers Lv. 2 "배달" (5) | 2025.06.18 |
| [C++] Programmers Lv. 3 "양과 늑대" (0) | 2025.06.17 |