6116 : 단지 번호 붙이기
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정사각형 지도가 주어집니다. 1은 집이 있는 곳을, 0은 집이 없는 빈곳을 나타냅니다.
상하좌우로 연결되어 있는 집들의 묶음을 하나의 '단지'라고 정의할 때, 단지 수를 구하고 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하십시오.
상하좌우로 연결되어 있는 집들의 묶음을 하나의 '단지'라고 정의할 때, 단지 수를 구하고 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하십시오.
입력 설명
첫째 줄에 지도의 크기 N (1 ≤ N ≤ 25)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 지도의 정보(0 또는 1의 붙여서 입력된 행 문자열)가 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 지도의 정보(0 또는 1의 붙여서 입력된 행 문자열)가 주어집니다.
출력 설명
첫째 줄에 총 단지 수를 출력합니다.
둘째 줄부터 각 단지별 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력합니다.
둘째 줄부터 각 단지별 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
7
8
9도움
각 칸을 순회하며 방문하지 않은 1을 만나면 BFS 탐색을 시작하여 연결된 1들의 칸 수를 세어 목록에 추가한 뒤 정렬하여 출력하십시오.