단지 번호 붙이기

면접 대비

시간 제한1초메모리 제한128 MB

요약
이진 격자에서 상하좌우로 연결된 1의 집합(단지) 개수와 각 단지의 크기를 오름차순으로 출력합니다.
난이도

쉬움10점 중 3점

유형
BFS, 그래프, 배열
정답자
아직 제출이 없습니다

문제

정사각형 지도에서 1은 집이 있는 칸, 0은 집이 없는 칸을 뜻한다. 집이 있는 두 칸이 위, 아래, 왼쪽, 오른쪽으로 맞닿아 있으면 서로 연결되어 있다고 한다. 대각선으로만 닿은 경우는 연결된 것이 아니다.

서로 연결된 집들의 모임을 하나의 단지라고 할 때, 지도를 보고 단지의 개수와 각 단지에 속한 집의 수를 구하시오. 각 단지의 집 수는 오름차순으로 정렬해 출력해야 한다.

입력

첫째 줄에 지도의 크기 N이 주어진다. 지도는 N x N 정사각형이며, 5 <= N <= 25이다.

둘째 줄부터 N개의 줄에는 지도의 각 행이 주어진다. 각 행은 0 또는 1로 이루어진 길이 N의 문자열이다.

출력

첫째 줄에 단지의 총개수를 출력한다.

그다음 줄부터 각 단지에 속한 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    7
    0110100
    0110101
    1110101
    0000111
    0100000
    0111110
    0111000
    
    예상 출력
    3
    7
    8
    9