1379: [창의적 알고리즘(중급)] 두더지 굴(S)
[만든사람 : 전민우(2009), 전현석(설명수정/채점데이터, 2021)]
문제 설명
영일이는 땅 속의 굴이 모두 연결되어 있으면 한 마리의 두더지가 사는 집이라는 사실을 알아냈다.
영일이는 마을 뒷산에 사는 두더지가 모두 몇 마리인지 궁금해졌다.
영일이는 특수 장비를 이용해서 뒷산에 있는 두더지 굴의 상태를 모두 찍은 지도를 만들 수 있었다.
지도는 직사각형인데 흙은 0으로 나타내고, 굴은 1로 나타낸다.
만약, 두더지 굴이 위-아래-왼쪽-오른쪽 어느 한쪽으로라도 연결되어 있으면, 그건 두더지 한 마리가 사는 집이라고 볼 수 있다.
[그림 1]과 같은 두더지굴 지도를 이어붙여 그리면서 서로 다른 번호를 붙이면, [그림 2]와 같이 두더지 굴의 개수와 두더지 굴의 크기를 눈으로 알아볼 수 있다.
특수 촬영 사진 데이터를 입력받아 두더지 굴의 수를 출력하고, 각 두더지 굴의 크기를 오름차순으로 정렬하여 출력하는 프로그램을 작성해보자.
입력 설명
첫 번째 줄에 두더지 굴의 가로, 세로의 크기를 나타내는 n이 입력된다.
두 번째 줄부터 n줄에 걸쳐 n개씩의 0 또는 1의 사진 데이터가 입력된다.
(1<=n<=10)
(0<=k<=1)
두 번째 줄부터 n줄에 걸쳐 n개씩의 0 또는 1의 사진 데이터가 입력된다.
(1<=n<=10)
(0<=k<=1)
출력 설명
첫 번째 줄에 두더지 굴의 개수를 출력하고
두 번째 줄부터 각각의 두더지 굴의 크기를 한 줄에 한 개씩 내림차순으로 출력한다.
두 번째 줄부터 각각의 두더지 굴의 크기를 한 줄에 한 개씩 내림차순으로 출력한다.
입력 예시 Copy
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
출력 예시 Copy
3
9
8
7
도움
- 창의적 알고리즘(중급)