https://www.acmicpc.net/problem/2583
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))
근데 둘의 차이는 잘 모르겠다... 왜지
'알고리즘' 카테고리의 다른 글
백준)블랙잭 (0) | 2023.02.20 |
---|---|
프로그래머스)문자열 나누기 (0) | 2023.02.19 |
프로그래머스)2개 이하로 다른 비트 (0) | 2023.02.17 |
프로그래머스)[1차] 프렌즈 4블록 (0) | 2023.02.16 |
프로그래머스)[3]차 n진수 게임-python (0) | 2023.02.16 |