BOJ 32122 밤양갱

문제 링크입니다.

문제 요약

$N \times N$ 격자의 각 칸에 $1$부터 $N^2$까지의 서로 다른 정수가 적혀 있습니다. 격자에서 겹치지 않도록 $i$개의 도미노를 얻었을 때 도미노에 적힌 $2i$개의 수들 중 최댓값을 $t_i$라고 합시다. $t_1, \cdots , t_{N^2/2}$의 최솟값을 각각 구하세요.

풀이

문제의 세팅과 반대로, $1$부터 $K$까지의 수가 적힌 칸만 이용해서 만들 수 있는 도미노의 최대 개수를 고려합니다. 칸 하나를 추가했을 때 만들 수 있는 도미노의 수는 유지되거나 추가된 칸을 사용하는 도미노를 추가해 정확히 하나 늘어나므로, $N^2$개의 값을 모두 구하면 원래 문제의 답 역시 모두 구해집니다.

새로운 칸을 추가했을 때 해당 칸을 사용하는 새로운 도미노를 찾는 작업은 격자 그래프에서 매칭을 찾는 것으로 볼 수 있습니다. 이분 매칭하면 보통 쓰는 Kuhn’s Algorithm이 애초에 Incremental하게 매칭을 찾는 이분 매칭 알고리즘이라 우리가 지금 하고 싶은 작업을 정확히 구현해줍니다.

$1$부터 $N^2$까지의 수가 적힌 칸을 순서대로 추가해 주면서, 새로운 매칭이 생길 때마다 답을 적어주면 ${\cal O}(N^4)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int dy[] = {0,1,0,-1}, dx[] = {1,0,-1,0};
int Y[12345], X[12345], match[12345], n;
vector<int> e[12345];
bool vis[12345], ingraph[12345];

inline int zip(int y, int x){return (y-1)*n+x;}

bool dfs(int now){
	for(auto nxt : e[now]){
		if(vis[nxt]) continue;
		vis[nxt] = 1;
		if(!match[nxt] || dfs(match[nxt])){
			match[nxt] = now;
			match[now] = nxt;
			return 1;
		}
	}
	return 0;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){
		int k; cin >> k;
		Y[k] = i; X[k] = j;
	}
	int last = 0, now = 0;
	for(int k = 1; k <= n*n; k++){
		int y = Y[k], x = X[k];
		ingraph[zip(y, x)] = 1;
		for(int dir = 0; dir < 4; dir++){
			int ny = y+dy[dir];
			int nx = x+dx[dir];
			if(ny <= 0 || ny > n || nx <= 0 || nx > n) continue;
			if(!ingraph[zip(ny, nx)]) continue;
			e[zip(y, x)].push_back(zip(ny, nx));
			e[zip(ny, nx)].push_back(zip(y, x));
		}
		memset(vis, 0, sizeof(vis));
		now += dfs(zip(y, x));
		if(last != now) cout << k << '\n';
		last = now;
	}
}