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

Problem

주어진 직사각형별 좌표중에 나누어지고 남은 영역의 개수와 크기를 구하는 문제

Solution

1)좌표가 x,y 들어오는데 이를 거꾸로 받기
2)for문을 통해 체크
3)dfs

코드설명

1)배열을 위에서 부터 체크해도 결과는 다르지 않을거 같아,
그냥 y,x를 거꾸로 받은 다음 배열의 순서대로 for문을 돌림
2)visited배열을 통해 방문한 배열을 제외한 나머지를 dfs처리
3)영역의 나머지 부분의 크기 및 영역 크기 계산

※참고로 default recursion limit 값이 10 ** 4여서 그런지 그냥 하면 오류
=>sys.setrecursionlimit(10 ** 6)으로 설정함.

대체 이 기준을 어떻게알지...?? 시험에 나오면 TC만 맞으면 그냥 맞았다고 생각하고 넘어갈거같은데 ㅠㅠ

Python Code

import sys
sys.setrecursionlimit(10**6)
M,N,K=map(int,sys.stdin.readline().split())

arrList=[]
dy=[0,-1,0,1]
dx=[-1,0,1,0]
result=[]
visited=[[False] * N for _ in range(M)]
for _ in range(M):
    tmpList=[0]*N
    arrList.append(tmpList)
for _ in range(K):
    a,b,c,d=map(int,sys.stdin.readline().split())
    for i in range(b,d):
        for j in range(a,c):
            arrList[i][j]+=1

def dfs(y,x):
    visited[y][x]=True

    for i in range(4):
        tmpy=y+dy[i]
        tmpx=x+dx[i]

        if tmpy<0 or tmpx<0 or tmpy>M-1 or tmpx>N-1:
            continue
        if arrList[tmpy][tmpx]==0 and not visited[tmpy][tmpx]:
            result[len(result)-1]+=1
            dfs(tmpy,tmpx)

for i in range(0,len(arrList)):
    for j in range(0,len(arrList[i])):
        if arrList[i][j]==0 and not visited[i][j]:
            result.append(1)
            dfs(i,j)
print(len(result))
result.sort()
for re in result:
    print(re,end=' ')