[백준] 2583번: 영역 구하기 - python

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

2583번: 영역 구하기

 

좌표 설정하는데 미로찾기처럼 위에서부터 0인줄알고 했다가 다시 읽어보니 거꾸로 되어있었어서 햇갈렷던 문제;

 

좌표를 색칠한 후에 나머지를 1로 모조리 칠해버리는 식으로 코드를 구현햇다.

 

만약 0이면 색칠 -> sum, cnt 증가 후 마지막에 정렬 후 출력 

 

sum = 0이면 1로 한 이유는 파고 들어가야지만 넓이가 증가되어 기본 첫번째 진입일때도 넓이가 1로 카운트 되게 설정하였다.

 

from collections import deque
m, n, k = map(int, input().split())
#m이 세로 n은 가로 즉 m은 x n은 y
arr = [[0 for _ in range(n)] for j in range(m)]
dx = [1, 0, -1 ,0]
dy = [0, 1, 0, -1]
cnt = 0
answer = []
dq = deque()

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())

    for i in range(y1, y2):
        for j in range(x1, x2):   
            arr[i][j] = 1


for  i in range(m):
    for j in range(n):
        if arr[i][j] == 0:
            sum = 0
            cnt+=1
            dq.append((i, j))
            
            while dq:
                x, y = dq.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]

                    if 0<=nx<m and 0<=ny<n:
                        if arr[nx][ny] == 0:
                            arr[nx][ny] = 1
                            dq.append((nx,ny))
                            sum+=1
            if sum == 0:
                sum = 1
            answer.append(sum)

answer.sort()
print(cnt)
print(*answer)

 

완성