> 문제 <

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

> 아이디어 <

< 방문하지 않은 [상, 하, 좌, 우] 의 값이 1이라면, 집의 수를 +1 해준다.
만약, 더이상 방문하지 않은 1이 없다면 bfs 혹은 dfs를 종료. > function code

함수 종료 == 한 단지 방문 완료
home 리스트에 집의 수(count)를 append 해주고,
방문하지 않은 1이 있는 좌표의 위치를 다시 bfs 혹은 dfs에 넣어주고 위의 내용을 반복한다.

> 코드 <

# bfs 버전
from collections import deque

N = int(input())
space = []
visited = [[False]*N for _ in range(N)]
home = []                  # 각 단지 내의 집의 수
for i in range(N):
    space.append(list(map(int, input())))

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

def bfs(x, y):
    count = 1
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                visited[nx][ny] = True
                if space[nx][ny] == 1:
                    count += 1
                    queue.append((nx, ny))
    home.append(count)


for i in range(N):
    for j in range(N):
        if not visited[i][j] and space[i][j] == 1:
            bfs(i, j)

print(len(home))
for x in sorted(home):
    print(x)

# dfs 버전
N = int(input())
space = []
visited = [[False]*N for _ in range(N)]
home = []                  # 각 단지 내의 집의 수
result = []
count = 1				   # 집 count
for i in range(N):
    space.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y):
    global count
    visited[x][y] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and space[nx][ny] == 1:
            count += 1
            dfs(nx, ny)
    return count

for i in range(N):
    for j in range(N):
        if space[i][j] == 1 and not visited[i][j]:
            home.append(dfs(i, j))
            count = 1

print(len(home))
for x in sorted(home):
    print(x)