[백준/BOJ] 25201 보드 뒤집기 게임

문제 : 25201 보드 뒤집기 게임

25201번: 보드 뒤집기 게임

뒤집기 마법을 쓰게 되면 좌표 기준 2*2칸의 색상이 변하기 때문에

이때 결국 각 행과 열의 색상 개수는 언제나 짝수개만큼 변한다.

따라서 처음 격자판에서 행, 열의 색깔 개수를 저장하고

원하는 격자판의 상태와 비교했을때 홀, 짝이 달라진다면 불가능한 경우임을 알 수 있다.

 

이를 구현하기 위해 모든 좌표 입력에 대해 행, 열의 색깔 개수를 더해주고

홀-홀 이거나 짝-짝으로 입력되면 나머지 2를 했을때 0이어야 하므로

모든 칸의 개수를 체크해 다 짝수인지 확인해 주면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, arr[100005][2], chk=1;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=0;i<N+M;i++){
        ll a, b;
        cin >> a >> b;
        arr[a][0]++;
        arr[b][1]++;
    }
    for (int i=0;i<=100000;i++){
        if (arr[i][0]%2 || arr[i][1]%2)
            chk=0;
    }
    cout << (chk ? "YES" : "NO");
    return 0;
}