[BOJ] 영역 구하기

---

코드

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

def bfs(i, j):
    area = 0
    q = deque([(i, j)])
    visited[i][j] = 1
    while q:
        x, y = q.popleft()
        area += 1
        for d in [(0,1), (0,-1), (1,0), (-1,0)]:
            nx, ny = x + d[0], y + d[1]
            if 0 <= nx < m and 0 <= ny < n:
                if graph[nx][ny] == 0 and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
    return area
    
    
m, n, k = map(int, input().split())
graph = [[0]*n for _ in range(m)]
visited = [[0]*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):
            graph[i][j] = 1

ans1 = 0
ans2 = []
for i in range(m):
    for j in range(n):
        if graph[i][j] == 0 and not visited[i][j]:
            ans2.append(bfs(i,j))
            ans1 += 1

print(ans1)
print(' '.join(map(str,sorted(ans2))))

결과

풀이 방법

• 주어진 두 좌표를 통해 만들어지는 직사각형 영역을 1로 채워서 표시하고, 나머지 영역의 개수와 넓이는 bfs 알고리즘으로 풀이하였다.

---