[ BOJ / 파이썬 ] 2583 영역 구하기

 

누가봐도 bfs문제!

 

ㅡ

 

[1] 상자를 칠한다. (2중 for문으로 칠해주기)

: 1에서 전에 배운 누적합을 사용해볼까 헀는데 옹? input 최대값이 100밖에 안되길래 그냥 2중for문으로 칠했다.

대신 이미 칠해진 부분은 패스하도록 설정

 

[2] 안 칠해진 영역의 개수와 넓이를 구한다.(bfs 이용)

이 부분은 전형적인 bfs문제! 

 

ㅡ

 

: 사실 상자가 뒤집혀 있는데 영역 개수와 넓이 구하는 거라 뒤집힌 채로 그냥 구해도 괜찮을 것 같아 고대로 받아서 계산했다.

: 근데 이렇게 하니까 좌표값이 개인적으로 자꾸 헷갈렸다. 그래서 디버깅하느라 시간이 조금 소요되어서 아쉽다.

: 공간감각이 떨어져서 좌표에서 꼬이면 멘탈 나가는 것 같은데.. 흠.. 조심하자!

 

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

m, n, k = map(int, input().split())
board = [[0]*n for _ in range(m)]
visited = [[False]*n for _ in range(m)]
q = deque([])
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
count = 0
areas = []   

def bfs():
  area_size = 0
  while q:
    x, y = q.popleft()
    area_size += 1
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 0 and not visited[nx][ny]:
            q.append((nx, ny))
            visited[nx][ny] = True
  
  return area_size
  
def fill():
  for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):
      for j in range(x1, x2):
        if board[i][j] == 0:
          board[i][j] = 1


fill()
for i in range(m):
  for j in range(n):
    if board[i][j] == 0 and not visited[i][j]:
      q.append((i, j))
      visited[i][j] = True
      areas.append(bfs())
      count += 1
      
print(count)
for area in sorted(areas):
  print(area, end=" ")