코드 복사/붙여넣기 하는 당신이 아름답습니다.

2453 : 부서 배치

풀이

어떤 두 사람의 친하고 친하지 않고를 나타내는 관계가 있다.

관계는 항상 그래프로 표현할 수 있다.

이 문제에서 주어진 관계들을 그래프로 표현하면, 이 관계들이 여러 개의 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-11-14 12:43

Read more posts by this author