[백준] 2583 - 영역 구하기 / Python / 실버 1

🚩문제 주소

📄풀이

먼저 영역 배열을 만들고, 직사각형의 꼭짓점 좌표를 이용해서 영역 배열에 꼭짓점 사이의 영역을 1로 채워줍니다.

BFS 함수를 만들어서 0인 부분만 개수를 세어 리턴합니다.

영역이 0 이고, 방문 하지 않았다면, BFS를 하여 정답 배열에 개수를 저장합니다.

배열의 개수를 출력하고, 배열을 오름차순으로 정렬한 후 출력합니다.

👨‍💻코드

from collections import deque

M,N,K = map(int, input().split())
area = [[0]*N for _ in range(M)]
visited = [[False]*N for _ in range(M)]
for _ in range(K):
  x1,y1,x2,y2 = map(int, input().split())
  for i in range(y1, y2):
    for j in range(x1, x2):
      area[i][j] = 1

def bfs(a,b):
  dx, dy = [1,-1,0,0], [0,0,1,-1]
  q = deque()
  q.append([a, b])
  visited[a][b] = True
  cnt = 1
  while q:
    x,y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<M and 0<=ny<N and area[nx][ny] == 0 and not visited[nx][ny]:
        q.append([nx,ny])
        visited[nx][ny] = True
        cnt += 1
  return cnt

answer = []
for i in range(M):
  for j in range(N):
    if area[i][j] == 0 and not visited[i][j]:
      answer.append(bfs(i,j))

print(len(answer))
print(*sorted(answer))