문제를 보고
1. 모눈종이에서 색칠된 영역을 표시하기 (배열에서 1로 작성)
2. bfs로 분리된 영역 넓이를 count 하기
-> 아직 색칠되지 않은 영역을 queue에 추가하고, 큐에서 하나씩 꺼내며 다음을 수행:
1. 현재 꺼낸 영역과 붙어 있는 영역 중 색칠되지 않은 영역을 찾기
2. 색칠되지 않은 영역을 큐에 추가하고 해당 영역을 색칠 처리
3. 이러한 과저을 반복하여 서로 연결된 모든 영역을 탐색하며 넓이를 계산
mp = []
for i in range(m):
row = [0] * n
mp.append(row)
for i in range(k):
x1, y1, x2, y2 = map(int, input().split())
for j in range(x2 - x1):
for l in range(y2 - y1):
mp[y1 + l][x1 + j] = 1
s = []
for i in range(m):
for j in range(n):
if mp[i][j] != 1:
s1 = 0
q = []
q.append([i, j])
while len(q) > 0:
removed = q.pop()
s1 += 1
a = int(removed[0])
b = int(removed[1])
mp[a][b] = 1
if b + 1 < n:
if mp[a][b + 1] == 0:
mp[a][b + 1] = 1
q.append([a, b + 1])
if b > 0:
if mp[a][b - 1] == 0:
mp[a][b - 1] = 1
q.append([a, b - 1])
if a > 0:
if mp[a - 1][b] == 0:
mp[a - 1][b] = 1
q.append([a - 1, b])
if a + 1 < m:
if mp[a + 1][b] == 0:
mp[a + 1][b] = 1
q.append([a + 1, b])
s.append(s1)
s.sort()
print(len(s))
print(*s)
다른 사람들의 재귀 함수 풀이 방식:
1. 재귀 함수의 정의:
def(x좌표, y좌표, 재귀횟수)
2. 현재 좌표 (x,y)가 유효한 범위 (0,n) 과 (0,m) 안에 있어야 하고 색칠되지 않은 상태여야함
3. 조건을 만족하면 색칠 처리, 인접한 좌표에 대해 재귀 함수를 호출
-> 이때 재귀 횟수에 +1을 더하여 전달