풀이
어떤 두 사람의 친하고 친하지 않고를 나타내는 관계가 있다.
관계는 항상 그래프로 표현할 수 있다.
이 문제에서 주어진 관계들을 그래프로 표현하면, 이 관계들이 여러 개의 Connected Component로 나눠질 수 있다.
부서는 반드시 2개가 존재하니까, 컴포넌트마다 그룹1에 들어가는 사람 수와 그룹2에 들어가는 사람 수를 정할 수 있다.
이를 정하는 과정에서 모순이 발생하면 -1을 출력하고 종료해주면 된다.
여기까지 각 컴포넌트마다 두 그룹에 할당되는 인원 수를 정했다.
이제 한 그룹의 사람들을 부서1에 배치할지, 부서2에 배치할지 정해야한다.
부서 인원 차이를 최소화 해야 하는데, 냅색과 비슷한 느낌으로 다이나믹을 해주자.
dp[n][k] = n번째 컴포넌트까지 고려했을 때, k명을 배치할 수 있는지 여부
dp[n][k] = dp[n-1][k-group[n][1]] | dp[n-1][k-group[n][2]]
dp 배열을 int로 잡으면 메모리초과가 나니 bool 타입으로 선언해주자.
이제 dp[n][k/2]에서 가장 가까운 k를 찾으면 되고, 자잘한 처리가 좀 귀찮으니 유의하자.
코드
#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;
struct edg {
int idx, type;
};
int flag, chk[10001];
bool dp[5001][10001];
vector<edg> gph[10001];
pair<int, int> res[10001];
void dfs(int now, int prv, int type, int &cnt) {
if (gph[now].size() == 0) {
chk[now] = 0;
cnt--;
return;
}
chk[now] = chk[prv] * type;
chk[now] == 1 ? res[cnt].fst++ : res[cnt].snd++;
for (edg nxt : gph[now]) {
if (flag) return;
if (!chk[nxt.idx]) {
dfs(nxt.idx, now, nxt.type, cnt);
}
if (chk[nxt.idx] == -chk[now]*nxt.type) {
flag = 1;
return;
}
}
}
void process() {
int n, m;
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= 10000; i++) {
gph[i].clear();
chk[i] = res[i].fst = res[i].snd = 0;
}
flag = 0;
scanf("%d %d", &n, &m);
while (m--) {
int t, u, v;
scanf("%d %d %d", &t, &u, &v);
gph[u].push_back({ v,t });
gph[v].push_back({ u,t });
}
queue<edg> que;
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (!chk[i]) {
chk[i] = 1;
dfs(i, i, 1, ++cnt);
}
}
if (flag) {
puts("-1");
return;
}
dp[0][0] = 1;
for (int i = 1; i <= cnt; i++) {
for (int j = 0; j <= n; j++) {
if (j-res[i].fst >= 0) dp[i][j] |= dp[i-1][j-res[i].fst];
if (j-res[i].snd >= 0) dp[i][j] |= dp[i-1][j-res[i].snd];
}
}
int mn = 1e9;
int no = 0;
for (int i = 1; i <= n; i++) {
if (!chk[i]) no++;
if (!dp[cnt][i]) continue;
if (abs(n/2-i) < abs(n/2-mn)) mn = i;
if (abs((n+1)/2-i) < abs((n+1)/2-mn)) mn = i;
}
//printf("/ %d %d / ", mn, no);
int a = mn, b = n - mn - no;
if (a > b) swap(a, b);
if (a + no <= b) printf("%d\n", b - a - no);
else printf("%d\n", (no-(b-a))%2);
/*printf("\n---%d--\n",flag);
for (int i = 1; i <= cnt; i++) {
printf("%d: %d %d\n", i, res[i].fst, res[i].snd);
}
for (int i = 1; i <= n; i++) {
printf("%d ", chk[i]);
}*/
}
int main() {
for (int t = 5; t; t--) {
process();
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이