이번 문제는 깊이우선탐색으로 해결하였다. 우선 모눈종이를 나타내는 리스트 field를 0으로 채운 후, 직사각형의 영역을 1로 갱신한 뒤에 검사하려는 다음 눈금이 범위 내에 있고 직사각형의 범위가 아니라면 카운팅 변수를 1씩 증가시키며 재귀함수를 호출하는 방식으로 접근하였다. 검사한 눈금은 1로 갱신시킨다. 결론적으로 field는 1로 채워지게 된다. sys.setrecursionlimit()을 설정 안해줘서 재귀 에러가 발생하였다. 재귀 함수를 사용한다면 습관화하는 것이 좋을 것 같다.

• 최대 재귀 제한을 늘린다.
• dfs함수를 y, x, cnt를 인자를 갖도록 선언한다.
  -> 4가지 방향을 dy, dx에 짝지어 저장한다.
  -> field[y][x]를 1로 갱신한다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> 검사할 눈금의 인덱스를 ny, nx로 선언하고 4가지 방향으로 나아가도록 한다.
  --> 만약 ny, nx가 0보다 크거나 같고, ny가 m보다 작고, nx가 n보다 작을 경우 cnt를 dfs(ny, nx, cnt+1)로 갱신한다.
  -> cnt를 반환한다.
• m, n, k를 입력받는다.
• field를 m*n의 영역에 0으로 채운다.
• k번 반복하는 for문을 돌린다.
  -> 직사각형의 왼쪽 아래 좌표 lx, ly와 오른쪽 위의 좌표 rx, ry를 입력받는다.
  -> ly부터 ry-1까지 반복하는 i에 대한 for문을 돌린다.
  --> lx부터 rx-1까지 반복하는 j에 대한 for문을 돌린다.
  ---> field[i][j]를 1로 갱신한다.
• 결과를 저장할 리스트 result를 선언한다.
• m번 반복하는 i에 대한 for문을 돌린다.
  -> n번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 field[i][j]가 0일 경우 result에 dfs(i, j, 1)의 반환값을 넣는다.
• result의 길이를 출력한다.
• result를 오름차순 정렬한다.
• result를 언팩킹하여 출력한다.

Code

import sys
sys.setrecursionlimit(10**9)
def dfs(y, x, cnt):
    dy=[0, 0, 1, -1]
    dx=[1, -1, 0, 0]
    field[y][x]=1
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny>=0 and nx>=0 and ny<m and nx<n and field[ny][nx]==0:
            cnt=dfs(ny, nx, cnt+1)
    return cnt

m, n, k=map(int, input().split())
field=[[0]*n for _ in range(m)]
for _ in range(k):
    lx, ly, rx, ry = map(int, input().split())
    for i in range(ly, ry):
        for j in range(lx, rx):
            field[i][j]=1
result=[]
for i in range(m):
    for j in range(n):
        if field[i][j]==0:
            result.append(dfs(i, j, 1))
print(len(result))
result.sort()
print(*result)