의도된 시간복잡도
🔒시간 제한
1.000 S메모리 제한
512 MB제출 수
2정답 수
2정답률
100.000%
문제 설명
$N \times M$ 크기의 행렬 $A$가 주어진다. $A$를 구성하는 연결 요소의 개수와 각각의 크기를 구해보자.
$A$를 구성하는 연결 요소는 아래와 같이 정의된다.
- $A[i][j] = 1$이면 $A[i][j]$는 연결 요소이다.
- $A[i_1][j_1]$와 $A[i_2][j_2]$에 대해 $|i_1 - i_2|$ $+$ $|j_1 - j_2| = 1$이면 두 칸은 같은 연결 요소이다.
-
연결 요소의 크기란, 연결 요소를 구성하는 칸의 개수를 의미한다.
입력 설명
첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. $(1 ≤ N, M ≤ 300)$
둘째 줄부터 $N$개의 줄에 걸쳐 $A$의 각 행에 대한 정보가 공백으로 구분되어 주어진다. $(0 ≤ A[i][j] ≤ 1)$
$A$에 연결 요소는 반드시 존재함이 보장된다.
출력 설명
첫째 줄에 $A$를 구성하는 연결 요소의 개수를 출력한다.
둘째 줄에 $A$를 구성하는 연결 요소 각각의 크기를 공백으로 구분하여 출력한다. 만약 연결 요소의 개수가 $2$개 이상일 경우, 오름차순으로 크기를 출력해야 한다.
예시 1
입력
4 5
1 0 0 0 1
1 1 0 0 0
0 0 0 1 0
0 0 0 1 1
출력
3
1 3 3
기여
만든 사람 : pill27211