BOJ 34464 Grid and Numbers Game

문제 링크입니다.

문제 요약

$N \times M$ 크기의 격자에 칸마다 음이 아닌 수가 하나씩 써 있습니다. 두 플레이어는 번갈아 가며 칸 하나를 골라 거기 적힌 수에서 1을 뺍니다. 수가 음수가 되거나, 인접한 두 수의 값이 같아지게 만들면 집니다(초기 상태에서 인접한 두 수의 값은 모두 다릅니다.). 누가 이길까요?

풀이

게임을 어떻게 어떻게 진행하다 보면 결국 할 게 없어진 두 플레이어는 격자 상의 모든 극소 칸을 0까지 내리게 됩니다. 같은 이유로 나머지 중 극소를 1로 내리고, 그다음 극소를 2로 내리고…

해서, 사실 이 게임 최종 상태가 게임 진행 과정에 상관없이 정해져 있습니다. 이 최종 상태를 찾은 뒤, 거기까지 도달하는 데 필요한 총 턴 수의 홀짝성으로 승패를 판정하면 되겠네요.

최종 상태를 찾기 위해 적힌 수가 작은 칸부터 오름차순으로 탐색합니다. 각 칸의 주변 4칸 중, 이미 최종 상태에서의 값이 결정된 칸들의 최종 값을 확인해 그중 최댓값+1로 해당 칸의 최종 값을 정하면 됩니다. 구현의 편의성을 위해 초기에 최종 상태 값을 모두 -1로 설정하는 것을 추천합니다. 방문 여부를 체크할 필요가 없어져요. 격자의 바깥쪽 테두리까지 포함해주면 경계 처리도 할 필요가 없어집니다.

총 시간 복잡도는 정렬 때문에 ${\cal O}(NM \lg NM)$이 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const int dx[] = {0,0,-1,1}, dy[] = {-1,1,0,0};
void solve(){
	int n, m; cin >> n >> m;
	vector<vector<int>> a(n+2, vector<int>(m+2, 0));
	vector<vector<int>> d(n+2, vector<int>(m+2, -1));
	vector<array<int, 3>> v;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> a[i][j], v.push_back({a[i][j], i, j});
	sort(v.begin(), v.end());
	for(auto& [x, i, j] : v){
		for(int k = 0; k < 4; k++){
			int ni = i+dy[k], nj = j+dx[k];
			d[i][j] = max(d[i][j], d[ni][nj]+1); 
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) ans ^= (a[i][j]-d[i][j]);
	cout << (ans&1 ? "Yes\n" : "No\n");
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int T; cin >> T; while(T--) solve();
}