백준 25201번: 보드 뒤집기 게임 (Java)

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

25201번: 보드 뒤집기 게임

 

 

 

 

 

 

 

 

---

 

풀이

인터넷 서핑하다가 우연히 1줄 풀이를 보고, '그냥 구현만 해서 날로 먹을까?' 했는데 그러기엔 양심이 찔려서 정리했습니다.

 

곰곰컵 공식 풀이가 있습니다만, bijection 부분부터 모르겠어서 이와 유사한 문제인 Codeforces Global Round 2 C번 문제의 Editorial을 보고 이해했습니다.

 

다음 명제는 참입니다:

'곰곰이가 뒤집기 마법을 사용하여 현재 격자판에서 원하는 격자판으로 바꿀 수 있다 <=> 현재 격자판의 행, 열과 원하는 격자판의 행, 열에 있는 빨간색 칸의 parity(==홀짝성)이 같다.'

증명

=>) 뒤집기 마법을 수행해도, 격자판의 각 행, 열에 있는 빨간색 칸의 parity는 바뀌지 않습니다. 따라서, 원하는 격자판에 현재 격자판의 행or열과 parity가 다른 행or열이 있다면 원하는 격자판으로 바꿀 수 없습니다.

<=) 이 부분이 살짝 어려웠는데, ad-hoc 문제인 만큼 ad-hoc으로 접근해봅시다. 곰곰이는 마지막 행, 열을 제외한 (10^5-1) * (10^5-1)개 칸을 마법을 통해 원하는 격자판과 똑같이 만들 수 있습니다. 이렇게 만들고 마지막 행/열을 살펴보면, 두 격자판의 행/열에 있는 빨간색 칸의 개수의 parity가 동일하기에 같게 됩니다. 무릎을 탁 치게 만드는 아이디어입니다.■

 

따라서, 시작 격자판의 행/열마다 빨간색 칸의 개수 / 원하는 격자판의 행/열마다 빨간색 칸의 개수를 센 후, parity가 모두 동일한 지 체크하면 됩니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static final int INF = 100001;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        if ((M-N) % 2 != 0) {
            System.out.println("NO");
            return;
        }
        boolean[] curRow = new boolean[INF];
        boolean[] curCol = new boolean[INF];
        boolean[] endRow = new boolean[INF];
        boolean[] endCol = new boolean[INF];
        
        for (int i = 0; i < N; i++ ) {
            st = new StringTokenizer(br.readLine());
            curRow[Integer.parseInt(st.nextToken())] ^= true;
            curCol[Integer.parseInt(st.nextToken())] ^= true;
        }
        
        for (int j = 0; j < M; j++) {
            st = new StringTokenizer(br.readLine());
            endRow[Integer.parseInt(st.nextToken())] ^= true;
            endCol[Integer.parseInt(st.nextToken())] ^= true;
        }
        
        for (int i = 1; i < INF; i++) {
            if ((curRow[i] ^ endRow[i]) || (curCol[i] ^= endCol[i])) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
 
}