BOJ 32895 Glued Grid

문제 링크입니다.

문제 요약

슬라이딩 퍼즐에서 몇 칸을 장애물로 채웠습니다. 남은 칸들은 구멍 없이 잘 이어집니다. (엄밀히 말해, 처음에 오른쪽 아래 귀퉁이에 위치하는 빈 칸을 장애물이 없는 임의의 다른 칸으로 옮길 수 있습니다.)

이 퍼즐을 풀 수 있을 지 판정하세요.

풀이

장애물이 없는 슬라이딩 퍼즐을 풀 수 있는 지와 해당 퍼즐에 적힌 수를 나열한 수열에서의 inversion counting 값이 짝수임이 동치라는 게 알려져 있습니다. 여기에 장애물을 추가하면, 장애물의 위치에 따라 어떤 블록을 다른 원하는 위치로 옮길 수 없게 될 수 있습니다.

슬라이딩 퍼즐은 격자 그래프입니다. 여기서 장애물이 놓인 칸을 지우고 나머지 칸들을 간선으로 이어 봅시다. 빈 칸을 적당히 옮기면 그에 따라 주변의 블록들이 옮겨지게 됩니다. 이때 어떤 블록을 특정 방향으로 옮기고 싶다면, 빈 칸이 그 블록을 원위치시키지 않으면서 그 블록의 앞으로 갈 수 있는 우회로가 필요합니다. 이게 없다면 빈 칸이 원래 자리로 돌아오면서 옮기고자 했던 블록을 원위치시킬 수밖에 없습니다.

구체적으로 이는 퍼즐을 정점에 대한 BCC로 분할해서 생각해 볼 수 있다는 의미가 됩니다. 한 BCC에서 다른 BCC로 가는 우회로가 존재하지 않으므로, 퍼즐을 이루는 각 블록은 그 BCC 안에서만 움직일 수 있습니다. 즉 각 BCC를 독립적인 슬라이딩 퍼즐로 볼 수 있습니다. 빈 칸은 어느 BCC로든 옮길 수 있으므로 퍼즐을 움직일 수 없는 경우는 고려하지 않아도 좋습니다.

슬라이딩 퍼즐 판이 단일 BCC를 이룬다면 여전히 위의 inversion counting의 홀짝성으로 해의 존재성을 판별할 수 있습니다. 따라서 각 BCC 안에 들어있는 수의 집합이 그 BCC에 들어있어야 하는 수의 집합과 일치하는지, 또 그 inversion counting이 짝수인 지 확인해 주면 됩니다.

…만! 단절점들에 대한 처리가 남아 있습니다. 단절점들은 여러 개의 BCC에 속해 있으나, 실제로는 하나의 BCC에 해당하는 퍼즐 판에 귀속됩니다. 생각해 보면 처음으로 빈 칸과 같은 퍼즐 판에 속하게 될 수 있는 BCC 쪽으로 붙여 주어야 함을 알 수 있습니다. 이는 초기 상태에서 오른쪽 아래 귀퉁이 칸을 포함하는 BCC에서 시작하는 BFS를 통해 계산할 수 있습니다.

나머지 부분은 모두 선형 시간에 동작하므로 총 시간 복잡도는 각 BCC에서 inversion counting을 계산할 때의 ${\cal O}(NM \lg NM)$입니다.

코드

팀연습 중에 풀다가 업솔빙한 거라 BCC 템플릿을 팀노트에서 들고 왔습니다. 그 부분이 제 원래 코드 스타일이랑 좀 다를 수 있어요.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN 252525
const int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
vector<int> l[MAXN], b[MAXN], art[MAXN];
int lo[MAXN], v[MAXN], nn[MAXN], a[MAXN], original[MAXN];
int vis[MAXN], vb[MAXN], va[MAXN];
int cc, num, root;

void dfs(int n, int par){
	nn[n] = ++cc;
	lo[n] = min(lo[n], nn[n]);
	for(auto i:l[n]){
		if (i == par) continue;
		if (nn[i]){
			lo[n] = min(lo[n], nn[i]);
			continue;
		}
		dfs(i, n);
		lo[n] = min(lo[n], lo[i]);
	}
}
void dfs2(int n, int c, int p){
	if(c > root) b[n].push_back(c);
	v[n] = 1;
	for (auto i : l[n]){
		if (v[i] && nn[i] < nn[n] && i != p){
			continue;
		}
		else if (v[i]) continue;
		if (nn[n] <= lo[i]){
			num++;
			b[n].push_back(num);
			dfs2(i, num, n);
		}
		else dfs2(i, c, n);
	}
}
void bcc(int st){
	memset(lo, 1, sizeof(lo));
	dfs(st, 0);
	num = 0;
	dfs2(st, 0, 0);
}

void bfs(int st){
	queue<int> q;
	vis[st] = b[st][0];
	for(auto& B: b[st]){
		vb[B] = 1;
		for(auto& A : art[B]){
			if(vis[A]) continue;
			vis[A] = B;
			q.push(A);
		}
	}
	while(q.size()){
		int now = q.front(); q.pop();
		for(auto& B : b[now]){
			if(vb[B]) continue;
			vb[B] = 1;
			for(auto& A : art[B]){
				if(vis[A]) continue;
				vis[A] = B;
				q.push(A);
			}
		}
	}
}

inline int zip(int i, int j){return i*500+j;}

char board[543][543];

int fen[MAXN+100];
void upd(int i, int v){
	for(;i<=MAXN;i+=i&-i) fen[i]+=v;
}
int qry(int i){
	int ret = 0;
	for(;i;i-=i&-i) ret+=fen[i];
	return ret;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n, m; cin >> n >> m; memset(board, '#', sizeof(board));
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
		cin >> board[i][j];
		if(board[i][j] == '#') continue;
		if(board[i-1][j] != '#'){
			l[zip(i-1, j)].push_back(zip(i, j));
			l[zip(i, j)].push_back(zip(i-1, j));
		}
		if(board[i][j-1] != '#'){
			l[zip(i, j-1)].push_back(zip(i, j));
			l[zip(i, j)].push_back(zip(i, j-1));
		}
	}
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
		cin >> a[zip(i, j)]; original[zip(i, j)] = (i-1)*m+j;
	} a[zip(n, m)] = n*m;
	if(board[n-1][m] == '#' && board[n][m-1] == '#') return !(cout << "possible");
	
	bcc(zip(n, m));
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(b[zip(i, j)].size() > 1) for(auto& B : b[zip(i, j)]) art[B].push_back(zip(i, j));
	bfs(zip(n, m));

	for(int B = 1; B <= num; B++) art[B].clear();
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
		if(board[i][j] == '#') continue;
		if(b[zip(i, j)].size() > 1) art[vis[zip(i, j)]].push_back(zip(i, j));
		else art[b[zip(i, j)][0]].push_back(zip(i, j));
	}
	
	for(int B = 1; B <= num; B++){
		ll tmp = 0; int cnt = 0;
		for(auto& i : art[B]){
			tmp += cnt-qry(a[i]);
			upd(a[i], 1); cnt++;
			va[a[i]] = 1;
		}
		if(tmp&1) return !(cout << "impossible");
		for(auto& i : art[B]){
			if(!va[original[i]]) return !(cout << "impossible");
			va[original[i]] = 0;
			upd(a[i], -1);
		}
	}
	cout << "possible";
}