난이도

Silver 1

풀이 참고 유무

x

막힌 부분

x

문제

문제 바로가기

입력

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

출력

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

예제 입력

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

예제 출력

3
1 7 13

문제 검토

영역 탐지한다는 점에서 BFS와 DFS 둘 다 가능해보인다.
이번 문제는 DFS로 풀어보도록 하자.

풀이(python)

Python - 시간초과

import sys
sys.setrecursionlimit(10000000)
m,n,k=map(int,input().split())
stage=[[0 for _ in range(n)] for _ in range(m)]
for _ in range(k):
    lx,ly,rx,ry=map(int,input().split())
    for x in range(ly,ry):
        for y in range(lx,rx):            
            stage[x][y]=2      
cnt=0
def DFS(nx,ny):    
    global cnt
    if nx<0 or nx>=m or ny<0 or ny>=n or stage[nx][ny]==1 or stage[nx][ny]==2:      
        return
    #방문처리와 카운트    
    stage[nx][ny]=1
    cnt+=1
    DFS(nx-1,ny)
    DFS(nx,ny-1)
    DFS(nx+1,ny)
    DFS(nx,ny+1)    
    return
import heapq
ans=[]
for x in range(m):
    for y in range(n):        
        DFS(x,y)
        #빈 영역을 갔다 왔다면 ans에 push        
        if cnt>0:            
            heapq.heappush(ans,cnt)
        cnt=0
#오름차순 정렬    
ans.sort()
print(len(ans))
for x in ans:
    print(x, end=' ')    

방문처리를 할 때 count를 1씩 해주면 마지막에는 해당 영역의 넓이가 나오게 될 것이다.

걸린 시간

22:02

총평

기본적인 DFS문제이다.