[백준] 14671번 - 영정이의 청소 (Silver 1)

문제 링크

백준 14671번 - 영정이의 청소 (Silver 1)

문제 설명

N x M 크기의 바닥에 곰팡이가 있다.
이 곰팡이는 대각선 위 아래로 증식하며, 증식한 다음 원래 곰팡이가 있던 자리는 곰팡이가 사라진다.
단, 곰팡이가 사라지는 지점이자 증식되는 지점의 곰팡이는 증식된다.

곰팡이가 바닥 전체를 뒤덮는 시점이 생긴다면 YES를, 아니면 NO를 출력하시오.

정답 코드 및 설명

(i, j) 지점에 있는 곰팡이는 2번 증식 후에는 (i - 2, j - 2), (i - 2, j), (i - 2, j + 2), (i, j - 2), (i, j), (i, j + 2), (i + 2, j - 2), (i + 2, j), (i + 2, j + 2)로 퍼지게 된다.
이를 다시 정리하면, (i, j) 지점에 있는 곰팡이는 충분히 큰 짝수번 증식 후에는 i와 홀짝성이 같은 모든 a, j와 홀짝성이 같은 모든 b에 대해 (a, b)로 증식할 수 있다는 것이다.
또한, 충분히 큰 홀수번 증식 후에는 (i, j) 지점에 있는 곰팡이가 i와 홀짝성이 다른 모든 a, j와 홀짝성이 다른 모든 b에 대해 (a, b)로 증식할 수 있다는 뜻이기도 하다.

따라서, 곰팡이가 바닥 전체를 뒤덮는 시점이 생기려면 처음 곰팡이가 있던 지점들의 홀짝성만 체크하면 된다.
곰팡이가 있던 지점들이 (홀, 홀), (홀, 짝), (짝, 홀), (짝, 짝) 네 가지 경우를 모두 포함한다면 언젠가는 바닥 전체가 뒤덮이게 되는 것이다.

이를 코드로 구현하면 아래와 같다.
21행과 27행이 코드의 핵심적인 부분이라고 할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ14671 {
    int n, m;
    boolean[][] molds = new boolean[2][2];

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int x, y;
        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            molds[x % 2][y % 2] = true;
        }
    }

    void solution() throws IOException {
        input();
        if (molds[0][0] && molds[0][1] && molds[1][0] && molds[1][1])
            System.out.println("YES");
        else System.out.println("NO");
    }

    public static void main(String[] args) throws IOException {
        new BOJ14671().solution();
    }
}