📝 문제 정보#
문제 번역#
문제 설명#
사람들 간의 상호작용이 주어질 때, 정점이 사람들이고 두 사람이 서로 친구인 경우에만 그들 사이에 간선이 있는 그래프를 정의할 수 있습니다. 이러한 그래프를 소셜 네트워크라고 하며, 예를 들어 대학의 학생들이나 작은 마을의 주민들과 같은 모든 사람들의 집합에 대해 잘 정의됩니다. 최근 몇 년간 소셜 네트워크를 분석하는 완전한 과학 분야가 생겨났는데, 이는 사람들과 그들의 행동에 대한 많은 흥미로운 측면들이 이 친구 관계 그래프의 속성으로 가장 잘 이해되기 때문입니다.
문제 해결 수업의 학생들을 정점으로 하는 친구 관계 그래프가 주어졌을 때, 여러분의 과제는 수업의 학생들을 두 그룹 $A$와 $B$로 분해하되, 다음 세 가지 조건을 동시에 만족하도록 하는 프로그램을 작성하는 것입니다:
- 수업의 각 학생은 정확히 하나의 그룹 $A$ 또는 $B$에 속합니다.
- 각 그룹 내의 임의의 두 학생은 서로 친구입니다.
- 그룹 $A$와 $B$의 크기 차이, 즉 $∣∣A∣−∣B∣∣$가 가능한 한 작아야 합니다.
예를 들어, 아래 그림에 나타난 친구 관계 그래프가 주어졌다고 가정합니다. 학생들을 $A = {u_1, u_2, u_3, u_6}$와 $B = {u_4, u_5, u_7}$로 분해하는 것은 불가능한데, 이는 $u_2$와 $u_6$이 친구가 아니기 때문입니다. 반면에 $A = {u_1, u_2}$와 $B = {u_3, u_4, u_5, u_6, u_7}$로의 분해에서는 각 그룹 내의 임의의 두 학생이 서로 친구이지만, 두 그룹 간의 크기 차이($|2 - 5| = 3$)가 $A = {u_1, u_2, u_3}$와 $B = {u_4, u_5, u_6, u_7}$로의 분해에서의 차이($|3 - 4| = 1$)보다 큽니다. 마지막 분해가 우리가 원하는 최적의 분해입니다.
입력#
프로그램은 표준 입력에서 읽습니다. 첫 번째 줄에는 두 정수 $n$과 $m$이 주어지며, 각각 친구 관계 그래프의 정점의 개수와 간선의 개수를 나타냅니다. 여기서 $2 ≤ n ≤ 1,000$이고 $0 ≤ m ≤ \binom{n}{2}$라고 가정합니다. 정점은 $1$부터 $n$까지 인덱싱됩니다. 다음 $m$개의 줄에서 각 줄은 그래프의 간선 $(u, v)$를 나타내는 두 정수 $u$와 $v$를 포함합니다.
출력#
프로그램은 표준 출력에 출력합니다. 정확히 한 줄에 정수 하나를 출력합니다. 이 정수는 학생들이 위의 세 가지 조건을 만족하는 두 그룹으로 분해될 수 있는 경우 두 그룹 간 크기 차이의 최솟값이어야 하고, 그렇지 않으면 -1이어야 합니다.
🧐 관찰 및 접근#
- 간선이 연결되어있으면 같은 그룹이어야 한다
- 팀 편성 문제처럼, 여그래프를 만들면 좋겠다는 생각이 직관적으로 든다.
- 이번에는 여그래프가 연결그래프가 아닐 수 있으므로, 이후에 잘 나눠서 배낭문제 맛으로 하면 되지 않을까?
💻 풀이#
- 코드 (C++):
void solve(){
cin >> N >> M;
rep(i, 1, N+1) rep(j, 1, N+1) links[i][j] = true;
rep(i, 0, M){
int u, v;
cin >> u >> v;
links[u][v] = false;
links[v][u] = false;
}
rep(i, 1, N+1) color[i] = 0;
vector<pii> groups;
rep(i, 1, N+1) if(color[i] == 0){
int cnt1 = 0, cnt2 = 0;
color[i] = 1;
queue<int> q;
q.push(i);
while(!q.empty()){
int cur = q.front(); q.pop();
if(color[cur] == 1) cnt1++;
else cnt2++;
rep(nxt, 1, N+1){
if(!links[cur][nxt]) continue;
if(cur == nxt) continue;
if(color[nxt] == 0){
color[nxt] = 3 - color[cur];
q.push(nxt);
}
else if(color[nxt] == color[cur]){
cout << -1 << '\n';
return;
}
}
}
groups.push_back({cnt1, cnt2});
}
bag[0][0] = 1;
rep(i, 0, groups.size()){
auto [c1, c2] = groups[i];
rep(j, 0, N+1){
if(!bag[i][j]) continue;
bag[i+1][j + c1] = true;
bag[i+1][j + c2] = true;
}
}
int ans = 1e9;
rep(i, 0, N+1) if(bag[groups.size()][i]) ans = min(ans, abs((N - i) - i));
cout << ans << '\n';
}