BOJ 34680 Fox Buki

문제 링크입니다.

문제 요약

$1$부터 $N$까지의 카드가 $N$장씩 총 $N^2$장의 카드가 있고, $N$명의 사람이 이를 $N$장씩 나누어 갖고 있습니다. 사람들이 카드를 적당히 교환해, 모든 사람이 $1$부터 $N$까지의 카드를 $1$장씩 가지고 있도록 만들고자 합니다.

한 카드가 교환에 사용되는 횟수의 최댓값을 최소화하면서 이를 수행하세요. 총 교환 횟수를 최소화하는 것이 아닙니다!

풀이

교환할 필요가 없으면 교환을 하지 않아야 합니다. 이를 우선 예외 처리합시다.

각 플레이어가 1장씩 카드를 모아서 $1$부터 $N$까지의 카드가 모두 있는 덱을 하나 만들었다고 합시다. 이걸 한 사람한테 몰아주는 행동은 각 사람들의 카드 1장을 한 사람에게로 쏘는 화살표처럼 생각할 수 있습니다.

이러한 덱을 $N$개 만들어서 모든 사람들이 하나씩 나누어 가질 수 있다면, 모든 사람들은 $1$부터 $N$까지의 카드를 $1$장씩 가지고 있게 되고, 이때 각 카드는 $i$번 사람에서 $j$번 사람으로 이동하는 화살표를 정확히 하나씩 만듭니다. 자신에게로 돌아가는 화살표를 빼면 나머지는 양방향으로 한 쌍씩 존재하므로, 해당하는 두 카드를 교환하는 연산을 통해 각 카드 당 최대 1번만 교환해 사용해서 문제를 해결할 수 있습니다.

근데 덱 $N$개를 만드는 게 가능할까요?

네.

각 사람들과 카드의 종류를 하나의 정점으로, 총 $2N$개의 정점을 고려합니다. 어떤 사람이 가지고 있는 카드를 간선으로 이으면 이 그래프는 이분 그래프입니다. 나아가 중복 간선을 포함하여, 모든 정점이 정확히 $N$개의 간선과 연결되어 있습니다.

적당히 $k$명의 사람을 골랐다고 합시다. 해당하는 정점들은 총 $kN$개의 간선을 가집니다. 한편 $k$명의 사람들이 가지고 있는 카드의 종류가 $t$개라고 하면 해당하는 정점들에는 $tN$개의 간선이 연결되어 있습니다. 이때 $tN$개의 간선 중에는 $k$명의 사람들과 연결된 $kN$개의 간선이 모두 포함되어 있으므로 $kN \le tN$을 얻으며, 이는 $k \le t$를 의미합니다.

따라서 홀의 결혼 정리에 의해 각 사람이 카드를 1장씩 내서 덱 하나를 완성할 수 있습니다. 덱을 만드는 데 사용된 카드에 해당하는 간선을 지우면 모든 정점이 $N-1$개의 간선을 가진 상태와 같아지고, 귀납적으로 모든 카드를 사용해 덱 $N$개를 항상 만들 수 있습니다. 줄여 쓰면, $k$-regular 이분 그래프에서 $k$개의 disjoint한 이분 매칭을 찾을 수 있습니다.

따라서 이분 매칭을 $N$번 찾아 $N$개의 덱을 실제로 구성하는 방식으로 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
int e[123][123], cnt[123][123], ans[123][123], match[123], n;
bool vis[123];

bool dfs(int now){
	for(int i = 0; i < n; i++){
		int nxt = e[now][i]; if(nxt == -1) continue; nxt /= n; if(vis[nxt]) continue; vis[nxt] = 1;
		if(match[nxt] < 0 || dfs(match[nxt])){match[nxt] = now; return 1;}
	}
	return 0;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	cin >> n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> e[i][j], cnt[i][e[i][j]/n]++;
	bool flag = 0; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(cnt[i][j] != 1) flag = 1;
	if(!flag) return !(cout << 0);
	for(int t = 0; t < n; t++){
		memset(match, -1, sizeof(match));
		for(int i = 0; i < n; i++){memset(vis, 0, sizeof(vis)); assert(dfs(i));}
		for(int x = 0; x < n; x++){
			int i = match[x];
			for(int j = 0; j < n; j++){if(e[i][j] != -1 && e[i][j]/n == x){ans[t][i] = e[i][j]; e[i][j] = -1; break;}}
		}
	}
	
	cout << (n*n-n)/2 << '\n';
	for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++){
        if(ans[i][j] > ans[j][i]) swap(ans[i][j], ans[j][i]);
        cout << ans[i][j] << ' ' << ans[j][i] << '\n';
    }
}