문제

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

예제 입력 1

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

예제 출력 1

3
1 7 13

문제 이해

일반 DFS랑 다른 점은 연결정보가 graph에 포함되어 한번에 주는 게 아니라 각각의 정보를 따로 준다는 것이다. 직사각형의 끝 좌표 두 값을 주면 그걸 graph에 적용해서 DFS를 돌려야 한다. 방향벡터를 가지고 시뮬레이션 형식으로 돌려야 할 것 같다. 각각의 넓이는 그냥 DFS가 호출될때마다 count를 해주면 된다. 하나의 넓이도 1이니까 더 추가할 것은 없다.

DFS는 익숙하니 문제는 직사각형 적용과 좌표 시작값이 아래에서 시작한다는 것이다. 하지만 후자로 말한 (0, 0)의 위치가 다른 건 상관없다. 평소처럼 왼쪽 가장 위의 점을 시작점으로 잡아도 graph의 전체적인 모양만 뒤집어 질뿐이다. 어차피 넓이만 각각 리스트에 넣고 오름차순으로 정열시키면 그만이다. 그래서 순서는 중요하지 않다.

직사각형을 graph에 구현하는 것은 어렵지 않다.
각 사각형의 정보가 x1, y1, x2, y2 형태로 제공되고, 2번째 값이 항상 큰 값이다. 그렇기에 이중 반복문으로 시작점과 끝점에 넣어주면 간단하게 구현된다.

직사각형을 맵의 적용

M, N, K = map(int, input().split()) #M세로 N가로 K사각형 갯수

# 연결 정보 입력
graph = [[1] * N for _ in range(M)]
for i in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 0

for i in range(N):
    print(graph[i])

"""
출력:
[1, 1, 1, 1, 0, 0, 1]
[1, 0, 1, 1, 0, 0, 1]
[0, 0, 0, 0, 1, 1, 1]
[0, 0, 0, 0, 1, 1, 1]
[1, 0, 1, 1, 1, 1, 1]
"""

다음과 같이 상하반전된 상태로 적용이 된다.

이제 모든 준비가 끝났다.

코드 및 설명

# 백준 2583번 영역 구하기

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향벡터 동-서-남-북순
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def DFS(y, x):
    global visited, answer, temp_count
    # 방문처리
    visited[y][x] = True
    # 갯수 카운트
    temp_count += 1

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M and graph[ny][nx] and not visited[ny][nx]:
            DFS(ny, nx)

# 0. 입력 및 초기화
M, N, K = map(int, input().split()) #M세로 N가로 K사각형 갯수
visited = [[False] * N for _ in range(M)]
answer = []
count = 0

# 1. 연결 정보 입력
graph = [[1] * N for _ in range(M)]
for i in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 0

# 2. DFS호출
for i in range(M):
    for j in range(N):
        if graph[i][j] and not visited[i][j]:
            temp_count = 0
            DFS(i, j)
            answer.append(temp_count)
            count += 1

# 3. 구한 넓이 오름차순 정리
answer.sort()

# 4. 출력
print(count)
# join함수는 문자열 리스트형태만 넣어줘야 해서 형변환
print(" ".join(map(str, answer)))

join함수는 값으로 문자열 리스트 값을 넣어줘야 해서 map으로 형변환을 한다.