[백준 알고리즘] 2583. 영역구하기

 

 

 

 

이 문제는 좌표로 되어 있었서 조금 헷갈렸다.

 

그렇지만 영역을 구하는 문제이기 때문에 직사각형이 상하나 좌우로 뒤집어도 영역의 갯수는 변하지 않기 때문에

 

다루기 편하게 상하로 뒤집은 다음 사용해서 영역을 구했다.

 

 

 

 

 

 

 

M, N, K = map(int, input().split())
arr = [[0] * N for i in range(M)]
areas = []
delta = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def DFS(i, j):
    stack = [(i, j)]
    arr[i][j] = 1
    cnt = 1
    while stack:
        r, c = stack.pop()
        for dt in range(4):
            nr = r + delta[dt][0]
            nc = c + delta[dt][1]
            if 0 <= nr < M and 0 <= nc < N and arr[nr][nc] == 0:
                arr[nr][nc] = 1
                stack.append((nr, nc))
                cnt += 1
    return cnt

# 상하로 뒤집고, 직사각형 집어 넣기
for _ in range(K):
    x1, y1, x2, y2, = map(int, input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            if not arr[i][j]:
                arr[i][j] = 1

# 영역 찾기
for i in range(M):
    for j in range(N):
        if arr[i][j] == 0:
            area = DFS(i, j)
            areas.append(area)
areas.sort()
print(len(areas))
print(*areas)