문제
접근
2차원 BFS 문제이다.
영역 개수 검출 및 각 영역의 크기를 구하면 된다.
BFS를 수행한 횟수가 영역 개수가 되며, 각 BFS 내부에서 최초 방문을 수행한 횟수가 영역의 크기를 나타낸다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from collections import deque
def bfs(sy, sx):
dx = [0,0,1,-1]
dy = [1,-1,0,0]
q = deque()
q.append((sx, sy))
board[sy][sx] = 2
size = 1
while q:
nowx, nowy = q.popleft()
for x, y in zip(dx,dy):
nx = x + nowx
ny = y + nowy
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if board[ny][nx] == 1:
board[ny][nx] = 2
q.append((nx,ny))
size+=1
return size
n = int(input())
board = []
for i in range(n):
board.append([int(item) for item in input()])
ans = []
for i in range(n):
for j in range(n):
if board[i][j] == 1:
ans.append(bfs(i,j))
ans.sort()
print(len(ans))
for item in ans:
print(item)