[BOJ 25201 // C++] 보드 뒤집기 게임

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25201번 문제인 보드 뒤집기 게임이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25201 

25201번: 보드 뒤집기 게임

주어진 보드에 뒤집기 연산을 적용하더라도, 각 행의 빨간 색의 개수의 홀짝성은 변하지 않는다는 점을 관찰하자. 이를 이용하면 대응되는 각 행과 각 열의 빨간 색의 개수의 홀짝이 서로 다른 경우 뒤집기 마법만으로는 현재 보드를 목표 보드로 바꾸지 못한다는 것을 알 수 있다.

 

반대로 각 행과 각 열의 빨간 색의 개수의 홀짝이 같다면 뒤집기 마법만으로 현재 보드를 목표 보드로 바꿀 수 있다. 그 증명은 다음과 같다. (대회 중에 아래와 같은 엄밀한 증명을 하고 풀 필요는 없으니 가볍게 읽자.)

 

먼저, 보드의 임의의 (가로와 세로가 2 이상인) 직사각형 영역에 대하여 직사각형의 네 꼭짓점 칸들만 뒤집을 수 있다는 점을 관찰하자. 해당 직사각형 내에 존재하는 모든 2x2 영역을 전부 한 번씩 뒤집으면 각 꼭짓점만 뒤집히고 나머지 칸은 뒤집히지 않기 때문이다. 더 자세히 설명하면, 위와 같이 보드를 뒤집을 때 직사각형 영역의 꼭짓점 칸은 한번, (꼭짓점을 제외한) 변 위의 칸은 두번, 내부 칸은 네번씩 뒤집힌다는 점을 관찰하자.

 

이제, 현재 보드에서 1행 또는 1열에 있지 않은 모든 빨간 칸에 대하여 좌상단이 (1,1)이고 우하단이 해당 빨간 칸인 직사각형의 네 꼭짓점을 뒤집자. 또한, 목표 보드에서도 1행 또는 1열에 있지 않은 모든 빨간 칸에 대하여 위와 같은 행동을 하자.

 

위의 연산으로 바뀐 현재 보드와 목표 보드의 1행과 1열을 제외한 모든 칸이 노란색 칸임은 자명하다. 그리고 (첫 칸을 제외한) 1행의 각 칸은 그 열에 포함된 빨간 칸의 개수가 홀수였다면 빨간 색, 짝수였다면 노란 색일 것이다. 이는 (첫 칸을 제외한) 1열의 각 칸도 마찬가지이다. 첫 칸의 경우 전체 빨간 칸의 개수가 홀수였다면 빨간 색, 짝수였다면 노란 색일 것이다.

 

위의 내용을 이용하면, 두 보드의 대응되는 각 행과 각 열의 빨간 칸의 수가 서로 일치한다면 두 보드의 1행과 1열 또한 일치하게 된다는 점을 알 수 있다. 한 보드에 적용한 뒤집기 마법을 그대로 적용하면 다시 원래 상태로 돌아가므로, 현재 보드와 목표 보드에 사용한 뒤집기 마법을 현재 보드에 전부 사용하는 것으로 현재 보드를 목표 보드로 만들 수 있다.

 

위의 내용을 이용하여 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

bool R[100001], C[100001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M; cin >> N >> M;
	N += M;
	while (N--) {
		int x, y; cin >> x >> y;
		R[x] ^= 1, C[y] ^= 1;
	}

	bool ans = 1;
	for (int i = 1; i < 100001; i++) {
		if (R[i] || C[i]) ans = 0;
	}

	if (ans) cout << "YES";
	else cout << "NO";
}