2583.md

백준 2583번 영역 구하기

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

---

코드 설명

• in_range() 함수는 x좌표와 y좌표가 리스트 범위 밖으로 벗어났는지 확인하는 함수이다. 벗어나지 않았을 경우엔 True를 벗어났다면 False를 리턴한다.
• find() 함수는 bfs를 이용한 것으로, 상하좌우 이동을 위한 dxs, dys 방향키 리스트와 이동할 좌표를 저장한 q 리스트를 이용해 만들었다. 방문한 곳은 0으로 표시함으로써 재방문하지 않도록 표시한다.
• 넓이가 곧 칸의 개수이기떄문에 cnt 변수에 저장한 뒤 리턴해 size라는 넓이를 저장하는 리스트에 append 해주었다.
• 마지막으로 영역이 여러개기 때문에 이중 for문을 통해 find함수를 돌려주었으며, size 리스트의 크기가 곧 영역의 개수고, size 리스트를 오름차순한 뒤 출력했다.

소스코드

• 메모리 : 30864 KB
• 시간 : 92 ms

def in_range(x,y):
	return x >= 0 and x < m and y >= 0 and y < n

def find(x,y):
	dxs, dys = [0,0,1,-1], [1,-1,0,0]
	cnt = 0
	q = []
	q.append((x,y))
	matrix[x][y] = 0
	cnt += 1
	while q:	
		x, y = q.pop(0)
		for dx, dy in zip(dxs, dys):
			nx, ny = x + dx, y + dy
			if in_range(nx,ny) and matrix[nx][ny] == 1:
				matrix[nx][ny] = 0
				cnt += 1
				q.append((nx,ny))
	return cnt
	

m, n, k = tuple(map(int, input().split()))
matrix = [[1]*n for _ in range(m)]
size = []
for _ in range(k):
	sx, sy, ex, ey = tuple(map(int, input().split()))
	for r in range(sy, ey):
		for c in range(sx, ex):
			matrix[r][c] = 0


for i in range(m):
	for j in range(n):
		if matrix[i][j] == 1:
			size.append(find(i,j))


print(len(size))
size.sort()
for sz in size:
	print(sz, end=" ")