2022.02.19 [백준] (python 파이썬) 영역 구하기

 

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

2583번: 영역 구하기

---

풀이

 

1. m*n크기의 배열을 만든다.

2. 만든 배열에서 주어진 좌표에 맞게 사각형을 배열에 그린다.

3. for문을 돌려 사각형이 그려지지않은 부분을 찾은 뒤, bfs함수를 이용해 빈공간의 크기를 체크한다.

 

배열에서 그려진 사각형을 체크해야했다. 그래서 arr배열을 True로 초기화 시켜주었고, 사각형이 그려진 부분을 False로 바꿔주었다.

문제에서 사각형의 좌표를 줄때 왼쪽 아래가 0,0이 되게 했다. 하지만 우리가 쓰는 배열은 왼쪽위가 0,0이기 때문에 상하반전을 해서 문제를 해결했다. 그래서 사각형의 가로세로의 증가량을 _x,_y로 지정했고, 주어진 왼쪽아래의 좌표로 부터 증가량을 for문을 돌려 배열에 표시하였다. 

그리고 for문을 돌려 사각형이 그려지지않은 부분을 bfs함수를 돌렸고 각 빈공간의 크기를 측정했고 ans배열에 크기를 담았다. 

from collections import deque
 
m,n,k=map(int, input().split())
arr=[[True]*n for _ in range(m)]
ans=[]
for i in range(k):
    x1,y1,x2,y2=map(int,input().split())
    _x=x2-x1
    _y=y2-y1
    for j in range(_y):
        for l in range(_x):
            arr[y1+j][x1+l]=False
 
def bfs(x,y):
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    deq=deque()
    deq.append((x,y))
    arr[x][y]=False
    cnt=1
    while deq:
        x,y=deq.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<m and 0<=ny<n:
                if arr[nx][ny]==True:
                    deq.append((nx,ny))
                    arr[nx][ny]=False
                    cnt+=1
    ans.append(cnt)
 
 
for i in range(m):
    for j in range(n):
        if arr[i][j]==True:
            bfs(i,j)
ans.sort()
print(len(ans))
for i in ans:
    print(i,end=' ')