BOJ - 2583

백준 문제 링크
영역 구하기

❓접근법

1. BFS를 사용했다.
2. 모눈종이 위에 직사각형이 그려진 부분을 1,나머지를 0으로 하는 리스트를 생성한다.
3. bfs함수 내에서 좌표를 가져오면서 count +1 해주고,
   상,하,좌,우 새로운 좌표를 탐색하면서
   새로운 좌표의 값이 0이면 그 값을 1로 바꾸고 queue에 넣어준다.
   마지막은 return count
4. 모눈종이를 for문 2개로 돌면서 좌표의 값이 0이면 count = bfs(i,j)로 설정하고, answer에 count를 append해준다.
5. answer를 오름차순 정렬하고 길이와 원소를 출력한다.

👌🏻코드

from collections import deque

M,N,K = map(int,input().split())
lst = [[0] * N for _ in range(M)]

for _ in range(K):
    x1,y1,x2,y2 = map(int, input().split())
    
    for i in range(M - y2 , M - y1):
        for j in range(x1, x2):
            lst[i][j] = 1
            

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]

    
    count = 0
    lst[x][y] = 1 # visited의 역할
    
    while queue:
        x,y = queue.popleft()
        count += 1
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            
            if (0<=nx<M) and (0 <= ny < N) and (lst[nx][ny] == 0):
                lst[nx][ny] = 1
                queue.append((nx,ny))
                
    return count

answer = []

for i in range(M):
    for j in range(N):
        if lst[i][j] == 0:
            count = bfs(i,j)
            answer.append(count)
answer.sort()
print(len(answer))
print(*answer)

모눈종이 좌표를 리스트로 옮길 때 적절한 range를 찾느라 애먹었다..ㅋㅋㅋ