| 시간 제한 | 메모리 제한 |
| 2초 | 1024MB |
문제
사람들이 N행 M열의 직사각형 모양으로 모여 있다. 초기에 각각의 사람의 상태는 정상 체온이거나 저체온증이고, 낮과 밤을 지나면서 사람들의 상태가 변화한다.
- 낮은 따뜻하기 때문에 저체온증인 사람이 정상 체온으로 회복할 수 있는 기회이다. 어떤 사람과 사방으로 인접한 두 명 이상의 사람이 정상 체온이라면 따뜻한 체온을 나눠 받아 저체온증에서 정상 체온으로 회복된다. 어떤 사람이 정상 체온으로 회복된 후에는 같은 방법으로 인접한 다른 사람들이 정상 체온으로 회복할 수 있으며, 이러한 체온 회복 과정은 낮 사이에 충분히 많이 반복될 수 있다.
- 밤은 춥기 때문에 정상 체온인 사람들이 저체온증에 걸릴 수 있다. 단, 밤 사이에 새롭게 저체온증에 걸리는 사람은 K명 이하이다.
낮과 밤이 계속 반복되며 사람들이 저체온증에 걸리거나 정상 체온으로 회복된다고 생각해 보자. 어떤 사람은 안타깝게도 저체온증에서 정상 체온으로 영영 회복할 수 없을 것이고, 어떤 사람은 근처에 정상 체온인 사람이 충분하여 밤에 어떠한 K명이 저체온증이 되는 것을 반복하더라도 낮이 되면 정상 체온으로 회복할 수 있을 것이다.
첫날 낮 사람들의 상태가 주어질 때 낮과 밤이 충분히 많이 반복된 후 최악의 경우에도 낮이 되면 정상 체온을 유지할 수 있는 사람의 수를 구하여라.
입력
첫 번째 줄에 사람들이 모인 직사각형 모양에서 행의 개수 N과 열의 개수 M, 밤에 새롭게 저체온증에 걸릴 수 있는 사람의 수의 최댓값 K가 공백으로 구분되어 주어진다. (1 ≤ N,M ≤ 2,000; 1 ≤ K ≤ N × M)
두 번째 줄부터 N개의 줄에 각각 길이가 M인 문자열이 주어진다. 문자열에서 i번째 줄의 j번째 문자는 i번째 행 j번째 열에 위치한 사람의 초기 상태를 의미한다. O는 정상 체온, .는 저체온증을 나타낸다. 주어지는 모든 문자는 O 또는 .임이 보장된다.
출력
낮과 밤을 계속 반복하더라도 낮이 되면 정상 체온을 유지할 수 있는 사람의 수를 출력한다.
풀이
먼저 낮의 상황을 보자. 낮에는 인접한 4개의 칸에 2명의 정상 체온 사람이 있으면 정상 체온으로 돌아간다. 이 과정은 저체온증인 칸의 인접한 칸을 살펴보면 된다. 저체온증은 빈칸, 정상 체온은 o로 표시했다.
탐색 과정에서 빈칸을 발견한 경우, 인접한 4칸을 확인해 2칸 이상이 정상 체온이라면 해당 칸을 정상 체온으로 돌려놓고 인접한 나머지 빈칸을 새로운 탐색 범위에 포함한다. 이렇게 되면 하나의 빈칸을 최대 3번까지 탐색하게 되는데 이렇게 중복 탐색을 해야 하는 이유는 이렇다.
4행 5열이 주어졌다고 했을 때, 탐색을 1행 1열부터 진행한다고 했을 때, 3행 4열에 이르기까지 모든 빈칸들이 주변 정상 체온이 0~1개 이므로 넘어가게 된다. 그런데 3행 4열이 정상 체온으로 돌아오면 연쇄적으로 이전에 지나친 칸들이 모두 정상체온으로 돌아온다.
만약 주변에 정상 체온이 없는 칸이 있다고 할 때, 이 칸은 최초 탐색으로 그냥 지나치게 되지만 이후 탐색으로 인접한 2개의 칸이 정상 체온으로 돌아오게 되면 각각 1회씩 더 탐색하게 되고 마지막 탐색에서는 인접한 2개의 칸이 정상 체온이 되었기 때문에 정상 체온이 될 수 있다.
이렇게 낮 동안 탐색을 끝내고 정상 체온으로 전환이 끝나면 모든 정상 체온은 직사각형으로 분포하게 된다. 이제 밤이 되어 K명이 저체온증에 빠질 때, 다음 날 회복이 불가능한 경우를 보자.
노란색 부분이 모두 저체온증이 된다고 해도 낮이 되면 다시 정상 체온으로 돌아올 수 있다. 정상 체온으로 돌아올 수 없게 되려면 인접한 칸에 회복되는 칸을 포함해 정상 체온이 1명 이하로 남아야 한다. 직사각형을 이루는 가장 바깥쪽 하나의 열 또는 행이 모두 저체온증에 빠지게 되면 그 행 또는 열의 어떤 칸도 정상 체온으로 돌아올 수 없다. 따라서 직사각형의 짧은 변이 K보다 작거나 같다면 밤이 될 때마다 한 줄씩 저체온증에 빠지고 그 직사각형 전체는 모두 저체온증으로 바뀐다. 직사각형의 분포를 확인하고 가로, 세로의 길이 중 작은 값이 K보다 작거나 같다면 그 직사각형 전체가 저체온증이 된다.
정답 코드
import sys
from collections import deque
input = sys.stdin.readline
d = [(1,0),(0,1),(-1,0),(0,-1)]
N,M,K = map(int,input().split())
p = [list(input()) for _ in range(N)]
check = [[0] * M for _ in range(N)]
bfs = deque()
for i in range(N*M):
r = i//M
c = i%M
# 빈칸을 먼저 찾아서 bfs에 담는다.
if p[r][c] == '.':
bfs.append((r,c))
# 너비우선탐색
while bfs:
nr,nc = bfs.popleft()
nearby = 0 # 인접한 정상 체온의 수
blanks = [] # 인접한 빈칸의 좌표를 담을 리스트
for i in range(4):
dr = nr+d[i][0]
dc = nc+d[i][1]
if 0<=dr<N and 0<=dc<M:
if p[dr][dc] == '.':
blanks.append((dr,dc))
else:
nearby+=1
# 인접 정상 체온이 2이상인 경우
if nearby>=2:
p[nr][nc] = 'O'
while blanks:
bfs.append(blanks.pop())
recovered = 0
bfs.clear()
# 직사각형 분포 탐색
for i in range(N*M):
r = i//M
c = i%M
if p[r][c] == 'O' and check[r][c] == 0:
h,w = r,c
# 직사각형의 가로와 세로 구하기
while h < N and p[h][c] == 'O': h+=1
while w < M and p[r][w] == 'O': w+=1
for j in range(r,h):
for k in range(c,w):
check[j][k] = 1
# K보다 작은 변을 갖는 직사각형은 버림
if h-r > K and w-c > K:
recovered+=(h-r)*(w-c)
print(recovered)
