BFS DFS

import sys
from collections import defaultdict


def dfs(x, y, house_count):
    # 현재 위치를 방문 처리
    visited[(x, y)] = True
    house_count[0] += 1

    # 상하좌우 방향 정의
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # 상하좌우로 이동하며 연결된 집 찾기
    for direction in directions:
        nx, ny = x + direction[0], y + direction[1]
        if 0 <= nx < N and 0 <= ny < N and not visited[(nx, ny)] and map_data[nx][ny] == 1:
            dfs(nx, ny, house_count)

# 입력을 한번에 받아 처리
data = sys.stdin.read().strip().split()
N = int(data[0])
map_data = [list(map(int, data[i+1])) for i in range(N)]

visited = defaultdict(bool)
complexes = []

for i in range(N):
    for j in range(N):
        if map_data[i][j] == 1 and not visited[(i, j)]:
            house_count = [0]
            dfs(i, j, house_count)
            complexes.append(house_count[0])

complexes.sort()

print(len(complexes))
for complex_size in complexes:
    print(complex_size)

import sys
from collections import deque, defaultdict

def bfs(x, y):
    # 현재 위치를 방문 처리
    queue = deque([(x, y)])
    visited[(x, y)] = True
    house_count = 1

    # 상하좌우 방향 정의
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        cx, cy = queue.popleft()

        # 상하좌우로 이동하며 연결된 집 찾기
        for direction in directions:
            nx, ny = cx + direction[0], cy + direction[1]
            if 0 <= nx < N and 0 <= ny < N and not visited[(nx, ny)] and map_data[nx][ny] == 1:
                visited[(nx, ny)] = True
                queue.append((nx, ny))
                house_count += 1

    return house_count

# 입력을 한번에 받아 처리
data = sys.stdin.read().strip().split()
N = int(data[0])
map_data = [list(map(int, data[i + 1])) for i in range(N)]

visited = defaultdict(bool)
complexes = []

for i in range(N):
    for j in range(N):
        if map_data[i][j] == 1 and not visited[(i, j)]:
            complex_size = bfs(i, j)
            complexes.append(complex_size)

complexes.sort()

print(len(complexes))
for complex_size in complexes:
    print(complex_size)