세종시 천문대에서 전파망원경을 이용하여 천체를 관측한 사진을 찍었다. 이 사진은 m*m의 정사각형 크기로 별 신호가 있는 영역은 1, 그렇지 않은 영역은 0으로 표현된다. 다음은 4*4크기의 사진을 나타낸다.

위 사진에서 1로 표시된 부분은 별 신호가 있는 영역으로 모두 9개가 존재한다. 이 별 신호가 상, 하, 좌, 우로 연결되어 있는 것을 우리는 별그룹으로 정의했다. 위 사진의 별 그룹은 모두 세 개로 각 그룹을 a, b, c로 나타내면 다음과 같다.

천문대에서 관측한 사진을 정렬하는 방법은 다음과 같다. 1) 별그룹의 개수가 적은 사진을 먼저 나열한다. 2) 기준 1)이 같다면 별 신호 수가 많은 사진을 먼저 나열한다. 3) 기준 2)가 같다면 행우선 탐색을 기준으로 별이 먼저 존재하는 사진을 먼저 나열한다. 다음은 4*4 사진에서 행우선 탐색의 우선순위는 다음과 같다.

예를 들어 다음 두 사진의 경우는 다음과 같이 정렬할 수 있다.

기준 1)에 의해 사진1과 사진2 모두 별 그룹의 개수는 3개로 동일하다. 다음으로 기준 2)에 의해 별 신호의 개수는 8개로 동일하다. 마지막으로 기준 3)을 적용하기 위해 8개의 별의 위치를 정리하면 다음과 같다. 사진1 별의 위치 : [1, 3, 4, 5, 7, 9, 10, 13, 16] 사진2 별의 위치 : [1, 3, 4, 5, 7, 9, 10, 13, 15] 1 ~ 13번까지 별의 위치는 동일하고 사진1은 16번에 사진 2는 15에 별이 있으므로 사진2가 먼저 정렬된다. 따라서 정렬된 결과는 사진2, 사진1 순으로 나열 된다. 같은 크기의 N개의 별 사진을 입력 받아 기준에 따라 정렬 하는 프로그램을 작성해보자.

사진 정렬

문제 설명

입력

출력

예제

코드 제출

로그인

LOGIN