BOJ 34966 방바닥 정리하기

문제 링크입니다.

문제 요약

격자 위에 두 종류의 물건과 구멍이 있습니다. 각 구멍을 이동시켜 같은 종류의 물건을 제거할 수 있습니다. 다른 종류의 물건을 넘어갈 수는 없습니다. 구멍을 한 번 이동시킬 때 원하는 만큼 움직이면서 물건들을 지울 수 있습니다.

구멍을 움직여야 하는 최소 횟수를 구하세요.

풀이

구멍을 한 번 집었으면 지울 수 있는 물건은 싹 다 지워버리는 게 무조건 이득입니다. 또 같은 구멍을 두 번 연속해서 이동시킬 이유가 없습니다.

두 구멍을 어떻게 이동시켜도 서로 닿을 수 없는 경우는 모든 물건을 치우는 게 불가능하고, 그렇지 않다면 두 번의 이동 이내로 두 구멍이 만날 수밖에 없습니다.

두 구멍이 만난 이후에는 구멍이 합쳐진 셈 치고 상태를 바꿔야 하는 최소 개수로 접근을 해 볼 수 있습니다. 그러면 문제가 최단 경로 문제와 동등함을 알 수 있고, 다익스트라든 다이얼이든 구현하면 맞을 수 있습니다.

저는 A부터 움직이는 경우와 B부터 움직이는 경우로 나눠서 다이얼을 두 번 돌리는 풀이로 해결했습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
const int INF = 9998244353;
 
char a[1234][1234];
int Ax, Ay, Bx, By, n, m, d[1234][1234]; bool isa, isb;
 
int solve(int ay, int ax, int by, int bx, bool c){
	queue<int> q[3]; q[0].push(ay); q[0].push(ax);
	for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) d[i][j] = INF; d[ay][ax] = 0;
	int now = 0;
	while(q[0].size() || q[1].size() || q[2].size()){
		while(q[0].empty()) swap(q[0], q[1]), swap(q[1], q[2]), now++;
		while(q[0].size()){
			int y = q[0].front(); q[0].pop();
			int x = q[0].front(); q[0].pop();
			if(d[y][x] < now) continue;
			for(int dir = 0; dir < 4; dir++){
				int ny = y+dy[dir], nx = x+dx[dir];
				if(ny <= 0 || nx <= 0 || ny > n || nx > n) continue;
				int nd = d[y][x]+(a[ny][nx] == ('a'+(c^(now&1)))); if(a[ny][nx] == ('a'+!c) && !now) nd = 2;
				if(d[ny][nx] <= nd) continue; d[ny][nx] = nd; q[nd-now].push(ny); q[nd-now].push(nx);
			}
		}
	}
	if(d[by][bx] > 1) return INF;
	return now;
}
 
int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){
		cin >> a[i][j]; if(a[i][j] == 'A') Ay = i, Ax = j; if(a[i][j] == 'B') By = i, Bx = j;
		if(a[i][j] == 'a') isa = 1; if(a[i][j] == 'b') isb = 1;
	}
	if(!isa && !isb) return !(cout << 0);
	if(!isa || !isb) return !(cout << 1);
	int ans = INF; ans = min(ans, solve(Ay, Ax, By, Bx, 0)); ans = min(ans, solve(By, Bx, Ay, Ax, 1));
	if(ans == INF) ans = -1; cout << ans;
}