영역구하기

문제이해
M*N배열에서 직사각형이 있는 있는부분을 표시하고
직사각형이 없는 영역이 몇개인지,
그영역이 몇개의 칸인지 오름차순으로 출력

 

배열에서
0 2 4 4 (왼쪽아래좌표와,오른쪽위좌표주어질때) 그영역 칠하기 = ( x1,x2,y1,y2)
for i in (x1,x2):
    for j in (y1,y2):
        adj[j][i] = 1                      * j랑 i 순서구분

 

M,N,K = map(int,input().split())
adj = [[0]*N for _ in range(M)]
visited = [[0]*N for _ in range(M)]
di = [-1,0,1,0]
dj = [0,1,0,-1]


def dfs(x,y):
    stack = [(x,y)]
    visited[x][y] = 1
    area = 1
    while stack:
        (x,y) = stack[-1]
        for d in range(4):
            nx = x + di[d]
            ny = y + dj[d]
            if 0<=nx<M and 0<=ny<N and adj[nx][ny] == 0 and visited[nx][ny] == 0:
                stack.append((nx,ny))
                area += 1
                visited[nx][ny] = 1
                break
        else:
            stack.pop()

    lst.append(area)




for _ in range(K):
    x1,y1,x2,y2 = map(int,input().split())
    for i in range(x1,x2):
        for j in range(y1,y2):
                adj[j][i] = 1
cnt = 0
lst = []
for i in range(M):
    for j in range(N):
        if adj[i][j] == 0 and visited[i][j] == 0:
            cnt+= 1
            dfs(i,j)
print(cnt)
lst.sort()
for i in lst:
    print(i,end=' ')

 

 

<comment>

1.M이랑 N 바껴서 헷갈림...

2.직사각형 채우기 주의

3.1이없는 배열에서 0이면 영역cnt += 1하고 dfs돌려서 갯수세기