오늘 뭐했지

https://boj.ma/31782/t 

문제 조건에 따라 낮동안에 정상체온이 되는 사람들의 그룹은 반드시 직사각형 형태가 됩니다.

밤에는 K명이 저체온증이 되는데 만들어지는 직사각형들 중 가로 또는 세로의 길이가 K보다 작거나 같다면 그 변에 있는 모든 사람이 저체온증에 걸리게 하면 낮동안에 정상체온이 될 방법이 없으므로 그 직사각형 그룹은 모두 저체온증이 됩니다.

따라서 bfs 한 번으로 정상체온 그룹을 만들어주고,

그룹을 만날때마다 가로, 세로 사이즈를 구해서 모두 K보다 크다면 직사각형의 크기만큼을  정답에 추가해주면 됩니다.

총 시간복잡도는 O(NM)입니다.

코드(python)

import sys
from collections import deque
input = sys.stdin.readline

def in_range(a, b):
    return 0 <= a < n and 0 <= b < m

n, m, k = map(int, input().split())
board = [list(input().strip()) for _ in range(n)]
q = deque()
visited = [[False] * m for _ in range(n)]
dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(n):
    for j in range(m):
        if board[i][j] == 'O':
            q.append((i, j))
            visited[i][j] = True

while q:
    x, y = q.popleft()
    board[x][y] = 'O'
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if not in_range(nx, ny):
            continue
        if visited[nx][ny]:
            continue
        if board[nx][ny] == '.':
            cnt = 0
            for ddx, ddy in dxy:
                nnx, nny = nx + ddx, ny + ddy
                if not in_range(nnx, nny):
                    continue
                if board[nnx][nny] == 'O':
                    cnt += 1
            if cnt >= 2:
                q.append((nx, ny))
                visited[nx][ny] = True
visited = [[False] * m for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(m):
        if board[i][j] == 'O' and not visited[i][j]:
            garo = 0
            saero = 0
            x = i
            y = j
            while x < n and board[x][j] == 'O':
                x += 1
                saero += 1
            while y < m and board[i][y] == 'O':
                y += 1
                garo += 1
            q = deque()
            q.append((i, j))
            visited[i][j] = True
            while q:
                x, y = q.popleft()
                for dx, dy in dxy:
                    nx, ny = x + dx, y + dy
                    if not in_range(nx, ny):
                        continue
                    if visited[nx][ny]:
                        continue
                    if board[nx][ny] != 'O':
                        continue
                    q.append((nx, ny))
                    visited[nx][ny] = True
            if garo > k and saero > k:
                ans += garo * saero
print(ans)

가로세로 체크하며 이미 방문한 그룹을 다시 방문하지 않기 위해 BFS를 한 번 더 했는데 굳이 이렇게 하지 않고 더 효율적으로 하는 방법이 있습니다. 저는 비효율적으로 구현한것 같습니다.