BOJ: 2583

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.
M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

---

Solution

입력 구현

import sys
read = sys.stdin.readline

M, N, K = map(int, read().split())

l = [[0 for _ in range(M)] for _ in range(N)]

def draw(x1, y1, x2, y2):
  for i in range(x1, x2):
    for j in range(y1, y2):
      l[i][j] += 1

for k in range(K):
  a, b, c, d = map(int, read().split())
  draw(a, b, c, d)

• draw() 함수를 정의하여 입력 좌표에 따라 모눈종이 l에 직사각형 구현

BFS 구현

from collections import deque

cnt = 0
res = []
visit = [[False for _ in range(M)] for _ in range(N)]
q = deque()
v1 = [1, 0, -1, 0]
v2 = [0, 1, 0, -1]
for i in range(N):
  for j in range(M):
    if not visit[i][j] and l[i][j] == 0:
      sz = 0
      q.append((i, j))
      while q:
        x, y = q.popleft()
        for ii, jj in zip(v1, v2):
          nx, ny = x + ii, y + jj
          if 0 <= nx < N and 0 <= ny < M:
            if not visit[nx][ny] and l[nx][ny] == 0:
              visit[nx][ny] = True
              q.append((nx, ny))
              sz += 1
      cnt += 1
      res.append(sz)

• 모눈종이의 크기만큼 방문 여부를 확인할 변수 visit 정의
• 시작 지점에서 상하좌우로 이동 후 방문하지 않았고 색칠이 되어있지 않다면 너비 우선 탐색 및 영역의 넓이 sz 1 증가
• 모든 지점을 시작 지점으로 반복하고 너비 우선 탐색이 마친 후 영역의 수 cnt 1 증가

결과 출력

res.sort()
print(cnt)
for i in res:
  if i == 0:
    print(1, end = ' ')
  else:
    print(i, end = ' ')

• 영역의 크기가 1인 경우 구현한 너비 우선 탐색에서 0으로 인식하여 if문을 통해 예외 처리