[도전 5일차] 2453 부서 배치

문제 : BOJ 2453 부서 배치

문제 링크

사용 알고리즘 : 이분매칭

 

이분매칭이 무엇인지 이 문제를 통해 알았다.

 

풀이: 

1) 문제 설명

테스트케이스 수는 5개다. (외국 형식)

1~n의 사람들이 있다. m번 사람들 사이의 관계가 주어진다.

-1 1 2 는 1과 2는 적이라는 뜻이고

1 1 2 는 1과 2는 친구라는 뜻이다.

이 사람들은 KOI 회사에 배정된 신입 사원들인데, 2개 부서 중 하나로 들어가야 한다.

이때, 친구는 같은 부서에, 적은 다른 부서에 위치하도록 사람들을 배치해야 한다.

배치하는 방법 중에서 부서간 인원 수의 차이의 최솟값을 구하는 것이 목표다.

 

2) 풀이

 

1. 각 사람들을 그래프의 정점으로 생각하고 dfs 또는 bfs를 통해 친구 또는 적인 사람들의 팀을 정해준다.

예를 들어 1번 사람의 팀을 A라 생각했을 때, 1의 친구들은 팀 A가 되고 마찬가지로 적들은 팀 B가 된다.

이때 여기서 끝내는 것이 아니라 1번의 친구들과 적 각각에 대해 똑같은 짓을 반복해준다. 그러면 1과 전혀 관계가 없는 사람들을 제외한 모든 사람들의 팀이 정해질 것이다. dfs 코드는 다음과 같다. 

k는 현재 사람 , k가 정해질 팀은 t이다.

void dfs(int k,int t){
    if(chk[k]){
        if(chk[k]!=t)
            flag=1;
        return;
    }
    cnt--; chk[k]=t;
     t==1?A++:B++;
    for(int x : E[k])
        dfs(x,3-t);
    for(int x : F[k])
        dfs(x,t);
}

이제 이 사람들을 그룹이라 부르겠다. 이렇게 그룹 내에서 팀A와 팀B 인원수는 유일하다(탐색(dfs/bfs)를 시작하는 사람이 팀 A에 속해 있다고 가정했을 때). 각 그룹에 대해 인원수를 (팀A,팀B) 로 구조체에 저장하고, 모든 사람들에 대해서 이 그루핑을 반복한다.

chk를 각 사람이 어떤 팀에 속했는지 저장하는 배열이라 하자.

다음은 이를 수행하는 코드다.

for(int i=1;i<=n;i++){
    if(chk[i]) continue;
    A=0;B=0; //A,B는 인원수 저장
    dfs(i,1); // dfs(person, team name)
    if(flag)  // 관계 간 충돌이 발생하는가 dfs에서 확인한다.
    	break;
    grp.emplace_back(A,B); //그룹 각각의 인원수를 저장하는 pair 벡터
}

 

2. 이제 각각의 그룹에 대해서 배치를 시작해야 한다. 각각의 그룹은 독립적이기 때문에, 회사 전체의 팀 A, 팀 B(전역)에다가 그룹 내부의 팀들(지역)을 배치한다고 생각하자.

이때 회사 전체 팀 A와 팀 B의 인원수 차이가 최소가 되도록 분배하는 것이다.

 

예를 들어 우리가 그루핑을 다음과 같이 했다고 생각해보자.

A      B     C

(1,3) (2,4) (3,6)

1 + 2 + 3 || 3 + 4 + 6 과 같이 분배할 수 도 있고

1 + 2 + 6 || 3 + 4 + 3 과 같이 분배할 수도 있다. 중요한 것은 그룹 내에서는 서로 다른 팀에 들어가야 한다는 점이다.

이때 차이가 최소가 되는 분배는 9 와 10으로 분배하여 차이가 1이 되도록 하는 것이다.

 

그룹 숫자들의 합이 n이므로 가능한 최대의 차이는 n-2이다.

DT 식을 다음과 같이 정의하자.

 

DT[ i ] [ j ] => i번째 그룹까지 살펴보았을 때, 차이가 j만큼 날 수 있는지를 true/false으로 표시.

 

관계식은 다음과 같다.

그룹 내에서 인원수의 차이를 diff, abs(x)를 x의 절댓값이라 할 때

DT[0][0] = 1 , DT[i][j] = (DT[i-1][ abs( j - diff ) ] || DT[i-1][abs(j+diff)]) ;

그런데 이렇게 되면 10000*10000 배열을 만들어야 된다고 생각할 수 있다.

(그룹 최대 개수 : 10000 , 가능한 최대 차이 : 10000)

이때 DT[i] 를 채우기 위해 DT[i-1] 의 정보만 필요하므로 사실상 필요한 것은 직전 행 정보 뿐이다.

이는 i 인덱스를 2로 나누어서 저장하는 트릭을 사용하여 해결 가능하다.

 

피보나치 함수를 예로 들면. DT[i] = DT[i-1] + DT[i-2] 를 DT[i%3] = DT[(i+2)%3] + DT[(i+1)%3] 로 변형하는 식으로

DT[i%2][j]=DT[(i+1)%2][abs(j-diff)]||DT[(i+1)%2][abs(j+diff)];

처럼 사용하는 것이다.

이렇게 DT 테이블을 채운 후

마지막 그룹까지 확인했을 때 가능한 가장 적은 차이를 답으로 선정하면 된다.

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end());
const int INF = 1e9;
using namespace std;
vector<int> F[10001],E[10001];
vector<pair<int,int>> grp;
int t=5,n,m,chk[10001],cnt,flag;
int A,B;
bool DT[2][10001];
void init(){
    grp.clear(); 
    memset(DT,0,sizeof(DT));
    for(int i=1;i<=n;i++){
        E[i].clear(); F[i].clear();
        chk[i]=0;
    }
    flag=0;
}
void dfs(int k,int t){
    if(chk[k]){
        if(chk[k]!=t)
            flag=1;
        return;
    }
    cnt--; chk[k]=t;
     t==1?A++:B++;
    for(int x : E[k])
        dfs(x,3-t);
    for(int x : F[k])
        dfs(x,t);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    while(t--){
        cin>>n>>m;
        init();
        int a,b,c; 
        while(m--){
            cin>>a>>b>>c;
            if(a==1)
                F[b].push_back(c),F[c].push_back(b);
            else
                E[b].push_back(c),E[c].push_back(b);
        }
        for(int i=1;i<=n;i++){
            if(chk[i]) continue;
            A=0;B=0;
            dfs(i,1);
            if(flag)
                break;
            grp.emplace_back(A,B);
        }
        if(flag){
            cout<<-1<<'\n';
            continue;
        }
        DT[0][0]=1; int i=0,ans=-1;
         for(auto& p : grp){
             i++;
             int diff=abs(p.first-p.second);
             for(int j=0;j<=10000;j++)
                 DT[i%2][j]=DT[(i+1)%2][abs(j-diff)]||DT[(i+1)%2][abs(j+diff)];
         }
        for(int i=0;i<=10000;i++)
            if(DT[(grp.size())%2][i]!=0){
                ans=i;
                break;
            }
        cout<<ans<<'\n';
    }
}

 

이렇게 되면 시간복잡도가 N^2 이 된다. 채점은 50ms 대로 잘 되지만, 이론 상 1초에 근접한 시간복잡도이다.

 

이때 우리는 탐색 범위를 제한시켜주는 

int k=0;
for(auto& p : grp){
	i++;
	int diff=abs(p.first-p.second);
   	k+=diff;
	for(int j=0;j<=k;j++)
		DT[i%2][j]=DT[(i+1)%2][abs(j-diff)]||DT[(i+1)%2][abs(j+diff)];
}

트릭을 사용하여 시간을 줄일 수 있다.