장애물 인식 프로그램

문제

import sys
input = sys.stdin.readline

# 지도의 크기
N = int(input())

# 지도
Map = []

for i in range(N):
    Map.append(list(int(j) for j in input().rstrip()))

# 방문기록
visited = [[False for i in range(N)] for i in range(N)]

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 블록
block = [0]
# 총 블록 수
cnt = 0

# 깊이 우선 탐색
def dfs(x, y):
    visited[x][y] = True
    block[cnt] += 1
    # 연결된 장애물
    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 Map[nx][ny] == 1:
            dfs(nx, ny)

# 전체 순회하며 dfs 실행
for x in range(N):
    for y in range(N):
        if Map[x][y] == 1 and not visited[x][y]:
            cnt += 1
            block.append(0)
            dfs(x, y)


print(cnt)
# 정렬
block.sort()
for i in block:
    if i != 0:
        print(i)