본문 바로가기

알고리즘

백준)영역구하기

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

 

2583번: 영역 구하기

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

www.acmicpc.net

 

 

import sys
sys.setrecursionlimit(10000)

def dfs(x,y,count):
  arr[x][y] = 1

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

    if (0 <= nx < row) and (0 <= ny < col) and arr[nx][ny] == 0 and arr[nx][ny ] == 0 :
      count = dfs(nx,ny,count+1)
  return count

row, col, n = map(int,input().split())

arr = [[0] * col for _ in range(row)]

for _ in range(n):
  a = list(map(int,input().split()))
  for i in range(a[1],a[3]):
    for j in range(a[0],a[2]):
      arr[i][j] = 1

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

answer = []

for i in range(row):
  for j in range(col):
    if arr[i][j] == 0 :
      
      # count = dfs(i,j,0)
      # answer.append(count+1)
      answer.append(dfs(i,j,1))

print(len(answer))

print(*sorted(answer))

 

알고리즘과 방법은 맞았지만 시간초과...

그리하여 수정한 코드는

 

import sys
sys.setrecursionlimit(10000)

def dfs(y, x, cnt):
    graph[y][x] = 1
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] == 0:
            cnt = dfs(Y, X, cnt+1)
    return cnt
    
M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = []
for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            res.append(dfs(i, j, 1))
print(len(res))
print(*sorted(res))

 

근데 둘의 차이는 잘 모르겠다... 왜지