[백준-2583] 영역 구하기 - Python

 

 

 

 

문제 소개

 

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

 

 

 

사용한 알고리즘

 

 

BFS

 

 

 

 

 

 

Code 

 

import sys
import collections



#sys.stdin = open("input.txt", "r")

input=sys.stdin.readline

M , N , K = map(int,input().split(" "))
Arr =[]
for i in range(M):
    Arr.append([0]*N)
rect = []
for _ in range(K):
    rect.append(list(map(int,input().split(" "))))


def rectFill(list0) :
    for xi in range(list0[0],list0[2]):
        for yi in range(list0[1],list0[3]):
            #print(xi,yi)
            Arr[yi][xi]=1


for i in range(len(rect)):
    rectFill(rect[i])

AreaList = []
def bfs(x0,y0):
    Q = collections.deque([])
    Q.append([x0,y0])
    Area=1
    Arr[x0][y0]=2
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    while Q:
        cx,cy = Q.popleft()
        for k in range(4):
            newx=cx+dx[k]
            newy=cy+dy[k]
            if 0<=newx<M and 0<=newy<N and Arr[newx][newy]==0:
                Q.append([newx,newy])
                Arr[newx][newy] = 2
                Area += 1
    AreaList.append(Area)


for xx in range(M):
    for yy in range(N):
        if Arr[xx][yy]==0:
            bfs(xx,yy)

AreaList.sort()
print(len(AreaList))
print(*AreaList)

 

 

 

※ end