[백준] 2583번, 영역 구하기 (Python)

문제

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

2583번: 영역 구하기

 

코드

import collections

m, n, k = map(int, input().split()) # m 세로, n 가로
graph = [[0]*n for _ in range(m)]
check = [[False]*n for _ in range(m)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
count = 0
result = []

def bfs(x,y):
    total = 0
    queue = collections.deque()
    queue.append((x,y))
    while queue:
        total += 1
        check[x][y] = True
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if graph[nx][ny] == 0 and check[nx][ny] == False:
                    check[nx][ny] = True
                    queue.append((nx,ny))
    return total

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

for x in range(m):
    for y in range(n):
        if graph[x][y] == 0 and check[x][y] == False:
            result.append(bfs(x,y))
            count+=1
            
result.sort()
print(count)
for i in result:
    print(i, end=' ')

for문을 돌아 x1,y1, x2,y2에 범위를 입력받으면 graph에 범위안을 1로 채워준다.

그리고 1인 직사각형을 제외한 부분을 알고싶기 때문에 graph에서 0인 부분을 찾게 bfs를 돈다.

 

영역에 개수를 구하기 위해서 bfs함수를 시작할때마다 count를 더해주고

영역마다 안에 개수는 bfs에서 total로 while문이 반복될때마다 total에 더해주면 된다.