[백준_파이썬]2667번_단지번호붙이기

# 깊게 들어가니까 dfs사용

# 움직여야 하니까 방향설정
dx = [1, -1, 0, 0]
dy = dx[::-1]

n = int(input())
# map정보 입력받기
maps = [list(map(int, input())) for _ in range(n)]
# 방문했는지 확인하기 위한 행렬
visited = [[0] * n for _ in range(n)]

def dfs(x,y):
    global cnt

    #  이 함수가 발동 됐다는 것은 집이 있는 곳으로 온 것(집 1개) - 집 세기
    cnt += 1
    
    # 집이 있을 때, 해당 함수가 동작하는 것이므로 방문표시
    visited[x][y] = 1

    # 방향 탐색
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 범위 안에 있다면
        if 0 <= nx < n and 0 <= ny < n:
            # 집이 있고, 방문하지 않았다면
            if maps[nx][ny] == 1 and visited[nx][ny] == 0:
                # 더 깊게 가주기
                dfs(nx, ny)


# 한 단지 내에서 집의 갯수
cnt = 0
# 단지 내에 집이 몇개씩 있는지 담을 배열
houses = []
for i in range(n):
    for j in range(n):
        # 집이 있고, 방문하지 않았을 때만 dfs수행
        if maps[i][j] == 1 and visited[i][j] == 0:
            cnt = 0
            dfs(i, j)
            houses.append(cnt) # dfs함수를 통해 하나의 단지를 다 세고 온 것
            

print(len(houses))
houses.sort()
print('\n'.join(map(str, houses)))