[DFS] 백준 2583. 영역구하기

문제

: 그래프에서 사각형 좌표 입력받으면, 사각형을 제외한 부분의 넓이와 개수를 구하라

포인트

1. 좌표값과 행렬의 차이

2. DFS

3. 좌표값 두개로 사각형 그리기

 

xy 좌표따라 그래프 그리는 거에서 좀 걸렸다.

넓이까지 구하는 게 아니었으면 더 빨리 풀 수 있었는데, 넓이 구해야 돼서 범위를 모퉁이 +1 없이 정확하게 구해야해가지고 더 오래 걸렸다. 대신에 영역 연습, 행과 열 변수 연습에 좋았다..

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


m,n,k = map(int, input().split())
g = [[0]*(n) for _ in range(m)]

for _ in range(k):
    # x y x y
    lx,ly,rx,ry = map(int,input().split())
    # squares
    for x in range(lx, rx):
        for y in range(ly, ry):
            g[y][x] = 1

dx = [0,0,1,-1]
dy = [1,-1,0,0]
def DFS(x,y):
    global width
    if 0<=x<n and 0<=y<m and g[y][x]==0:
        g[y][x] = 9
        width += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            DFS(nx,ny)
        return True
    return False

cnt = 0
squares = []
for i in range(n):
    for j in range(m):
        width = 0
        if DFS(i,j) == True:
            cnt += 1
            squares.append(width)

print(cnt)
squares.sort()
for s in squares:
    print(s, end=' ')

 

90% 내힘으로 풀었다. 뿌-듯