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

출처 : https://www.acmicpc.net/problem/14671

 

문제

영정이는 숭실대 학교 앞, 원룸에서 자취를 한다. 원룸 자취방 방바닥에는 곰팡이가 서식하고 있는데, 곰팡이는 시간이 지날 때 마다 증식을 한다. 영정이의 자취방에서 서식하는 곰팡이는 특이한 방식으로 증식하는데, 어떤 한 지점에 곰팡이가 있었다면 그 위치에서 대각선 위 아래로 곰팡이가 증식되고 원래 곰팡이가 있던 자리는 곰팡이가 사라지게 된다. 아래 2번 그림과 같이 곰팡이가 사라지는 지점이자 다시 증식되는 지점이면 곰팡이는 증식된다.

영정이는 매우 게으름이 많아 미래에 이 곰팡이가 자신의 집을 모두 뒤덮는 시점이 한번이라도 생길 것으로 예측되면 대청소를 하려고 한다. 영정이의 집의 크기와, 현재 곰팡이의 위치가 주어질 때, 영정이가 청소를 해야 하는지 안 해도 되는지 알려주자.

 

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 영정이의 자취방 바닥의 크기 N과 M, 그리고 바닥에 있는 곰팡이의 개수 K가 주어진다. (2 ≤ N, M ≤ 1,000) (1 ≤ K ≤ 100,000) 둘째 줄부터 K줄에 걸쳐 현재 곰팡이의 위치 x, y가 주어진다. 좌표계는 행렬 좌표계와 일치한다. (1 ≤ x ≤ N) (1 ≤ y ≤ M) 곰팡이는 중복되지 않는 위치에 주어진다.

 

출력

프로그램의 출력은 표준 출력으로 한다. 영정이가 청소를 해야 한다면 ‘YES’를 청소를 하지 않아도 된다면 ‘NO’를 출력하자.

 

---

 

아이디어

탐색 유형 : 완전 탐색

곰팡이가 최대로 증식이될 때까지 계속해서 탐색을 진행하는 것이 기본 원리가 된다.

이에 따라 2가지 방식으로 탐색 범위를 지정할 수 있다.

 

1번째 : BFS를 통한 완전 탐색

• Queue에 곰팡이 좌표로 초기값을 세팅하여 탐색을 시작한다.
• 증식 조건이 참일 경우, 새로운 곰팡이를 Queue에 추가하는 과정을 반복.

 

2번째 : BFS 완전 탐색 최적화 - 탐색의 수학적 범위

먼저, 곰팡이가 전부 퍼지게 되는 특정 상황을 생각해보자.

• 곰팡이 증식 시, 원래 있던 자리는 제거되기 때문에 이를 보완할 다른 곰팡이가 존재해야 한다.
• 곰팡이는 상하좌우로 증식 불가능하다.

즉, 곰팡이를 전부 퍼지게 하기 위해서는 다음 사항이 필요하다는 것을 알 수 있다.

한 곰팡이를 기준으로 상하좌우를 증식시킬 한 쌍의 곰팡이가 존재해야 한다.

다시 말해, 상하좌우를 보완할 곰팡이 한 쌍 + 대각선을 서로 보완할 곰팡이 한 쌍 => 최소 4개 이상의 곰팡이가 존재해야 한다.

 

이 때 주의점으로 곰팡이 4개를 랜덤으로 넣어서는 안된다.

 

곰팡이가 퍼지는 방향의 x,y 값을 계산하면 다음과 같은 특징을 발견할 수 있다.

• x+y 합이 짝수 -> 증식 위치의 x+y 합은 짝수.
  • 상하좌우를 증식해줄 곰팡이 2개의 초기 위치는 다음과 같다.
  • -x+y 합이 짝수 and 한 곰팡이의 y값 홀수 and 다른 곰팡이의 y값 짝수
• x+y 합이 홀수 -> 증식 위치의 x+y 합은 홀수.
  • 상하좌우를 증식해줄 곰팡이 2개의 초기 위치는 다음과 같다.
  • -x+y 합이 홀수 and 한 곰팡이의 y값 홀수 and 다른 곰팡이의 y값 짝수

 

그러므로, 다음과 같이 알고리즘 계산식을 설정을 통해 문제를 일반화할 수 있다.

• y=홀수 and x+y=짝수
• y=짝수 and x+y=짝수
• y=홀수 and x+y=홀수
• y=짝수 and x+y=홀수

 

정답 코드

N,M,K=map(int,input().split())
C=[0]*4 # 곰팡이 4개
for _ in [0]*K:
    i,j=map(int,input().split())
    if i%2==1:
        if(i+j)%2==0:C[0]=1
        else:C[1]=1
    elif (i+j)%2==0:C[2]=1
    else:C[3]=1
print('YNEOS'[all(C)<1::2])