백준 [14671] 영정이의 청소(Python3)

문제 링크 : https://www.acmicpc.net/problem/14671

14671번: 영정이의 청소

완전 탐색

시간이 지날 때마다 곰팡이를 퍼뜨려, 곰팡이가 전부 퍼지는 때가 있는지 확인한다.
하지만, 특정 데이터셋의 경우, 시간이 아무리 지나도 곰팡이가 전부 퍼지지 않는다.
또한, 얼마나 시간을 두고 계산해야 할지에 대해 기준도 난해하다.

 

완전 탐색 최적화 - 탐색 범위 좁히기

곰팡이가 전부 퍼지게 되는 특정 상황을 찾아본다.

 

1. 곰팡이가 한번 퍼지면 원래 있던 자리는 비워지기 때문에, 이를 보완할 다른 곰팡이가 있어야 한다.

2. 곰팡이는 대각선으로 퍼지기 때문에 상하좌우를 채울 수 없다.
즉, 한 곰팡이를 기준으로 상하좌우를 채워줄 곰팡이 한 쌍이 필요하다.

정리하면, 상하좌우를 서로 보완할 곰팡이 한 쌍, 대각선을 서로 보완할 곰팡이 한 쌍이 있어야 하고, 이러면 최소 4개의 곰팡이가 있어야 빈틈없이 퍼뜨릴 수 있다.

 

근데 곰팡이 4개를 아무 위치에다 두면 안 된다.

 

곰팡이가 퍼지는 방향의 x, y값을 계산하면 다음 특징을 얻을 수 있다.
1. x + y의 합이 짝수면 퍼지는 위치의 x + y의 합은 짝수다.
2. x + y의 합이 홀수면 퍼지는 위치의 x + y의 합은 홀수다.

 

1번을 만족하면서 서로를 보완해줄 곰팡이 2개의 초기 위치는 다음과 같다.

- x + y의 합이 짝수이면서, 한 곰팡이는 y 값이 홀수, 다른 곰팡이는 y 값이 짝수

 

마찬가지로 2번을 만족하면서 서로를 보완해줄 곰팡이 2개의 초기 위치는 다음과 같다.

- x + y의 합이 홀수이면서, 한 곰팡이는 y 값이 홀수, 다른 곰팡이는 y 값이 짝수

 

요약하면 다음과 같다.

1. y는 홀수, x + y는 짝수
2. y는 짝수, x + y는 짝수
3. y는 홀수, x + y는 홀수
4. y는 짝수, x + y는 홀수

 

코드

N, M, K = map(int, input().split())

a, b, c, d = False, False, False, False
for _ in range(K):
    i, j = map(int, input().split())
    if i % 2 == 1:
        if (i + j) % 2 == 0:
            a = True
        else:
            b = True
    else:
        if (i + j) % 2 == 0:
            c = True
        else:
            d = True

if a and b and c and d:
    print("YES")
else:
    print("NO")