[Backjoon] 2583 영역 구하기 Python 문제 풀이

출처 : 영역 구하기

문제해석

• 모눈종이 전체 눈금을 0으로 초기화 한 뒤 사각형을 이루고 있는 부분을 1로 초기화해준다.

• 모눈종이 전체 눈금 한칸한칸을 탐색하는 기준으로 (0,0)부터 시작해서 흰색(0)을 이루고 있는 부분을 만나면 BFS/DFS 탐색을 시작함과 동시에 영역개수를 증가시킨다.

• 해당영역내에서 흰칸을 이루고 있는 부분만큼 영역넓이를 구해서 반환해준뒤 해당 넓이를 저장하는 리스트에 추가해준다.

• 최종적으로 구해진 영역 개수와 영역 넓이 리스트의 값들을 출력한다.

해답코드

import sys
from collections import deque

input = sys.stdin.readline

n, m, k = map(int, input().split())

maps = [[0]*m for _ in range(n)]

for _ in range(k):
    x1,y1,x2,y2 = map(int,input().split())
    for y in range(y1,y2):
        for x in range(x1,x2):
            maps[y][x] = 1

dy = [-1,1,0,0]
dx = [0,0,-1,1]

ans=1
area=[]

def bfs(startY,startX):
    global ans
    q = deque()
    q.append([startY,startX])
    maps[startY][startX]=2
    while q:
        y,x = q.popleft()
        for d in range(4):
            ny,nx = y+dy[d], x+dx[d]
            if 0<=ny<n and 0<=nx<m and maps[ny][nx]==0:
                ans+=1
                maps[ny][nx]=2
                q.append([ny,nx])
    return ans

for y in range(n):
    for x in range(m):
        if maps[y][x]==0:
            ans=bfs(y,x)
            area.append(ans)
            ans=1

area.sort()
print(len(area))
for result in area:
    print(result, end=" ")