[DFS, BFS] 백준 2583번: 영역 구하기 / 실버1

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

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

import sys
sys.setrecursionlimit(15000)
y_lim, x_lim, n = map(int,input().split())

graph = []
for i in range(x_lim):
    graph.append([0]*y_lim)

for i in range(n):
    x1, y1, x2, y2 = map(int,input().split())
    for j in range(x1,x2):
        for k in range(y1, y2):
            graph[j][k]=1

dx=[-1,1,0,0]
dy=[0,0,-1,1]

def dfs(x,y):
    graph[x][y]=1
    sum = 1
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<x_lim and 0<=ny<y_lim and graph[nx][ny]==0:
            sum += dfs(nx,ny)
    return sum

count = 0
answer = []
for i in range(x_lim):
    for j in range(y_lim):
        if graph[i][j]==0:
            answer.append(dfs(i,j))
            count+=1

answer.sort()
print(count)
print(*answer)

기본적인 dfs 문제!