주사위 던지기

면접 대비

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

요약
배경, 주사위, 점 픽셀로 그린 격자 그림에서 연결된 주사위 영역마다 그 안의 연결된 점 영역 개수를 세어 오름차순으로 출력한다.
난이도

보통10점 중 4점

유형
DFS, BFS, 그래프, 구현
정답자
아직 제출이 없습니다

문제

카메라로 던진 여러 개의 주사위를 사진으로 찍었을 때, 그 이미지만 보고 각 주사위에 나타난 눈(점)의 개수를 세어야 한다.

각 이미지는 세 종류의 픽셀로만 이루어진다. 배경 픽셀, 주사위 픽셀, 그리고 주사위 위의 눈(점) 픽셀이다. 두 픽셀은 변을 맞대고 있을 때에만 연결되어 있다고 하며, 꼭짓점만 맞닿은 경우는 연결로 치지 않는다.

픽셀 집합 SS가 연결되어 있다는 것은, SS에 속한 임의의 두 픽셀 aa, bb에 대해 SS 안의 픽셀 수열 a1,a2,…,aka_1, a_2, \dots, a_k가 존재하여 a=a1a = a_1, b=akb = a_k이고 모든 1≤i<k1 \le i < k에서 aia_i와 ai+1a_{i+1}이 서로 인접함을 뜻한다.

  • 주사위는 배경이 아닌 픽셀들의 극대 연결 집합이다(주사위 픽셀과 눈 픽셀 모두 배경이 아닌 픽셀로 취급한다). '극대'란 배경이 아닌 어떤 픽셀도 더 넣으면서 연결을 유지할 수는 없다는 뜻이다.
  • 눈(점)은 눈 픽셀들의 극대 연결 집합이다.

이미지에 있는 모든 주사위에 대해 각각 몇 개의 눈을 가지고 있는지 구하라.

입력

입력은 여러 장의 사진으로 이루어진다. 각 사진은 두 정수 ww와 hh가 적힌 줄로 시작하며, 각각 사진의 너비와 높이를 나타낸다(5≤w,h≤505 \le w, h \le 50).

이어지는 hh개의 줄에는 각각 정확히 ww개의 문자가 있다.

  • . 은 배경 픽셀,
  • * 은 주사위 픽셀,
  • X 는 눈(점) 픽셀이다.

주사위는 크기가 서로 다를 수 있고, 광학적 왜곡 때문에 완전한 정사각형이 아닐 수도 있다. 모든 사진에는 주사위가 적어도 하나 있으며, 각 주사위의 눈의 개수는 11 이상 66 이하이다.

입력은 첫 줄이 0 0인 사진으로 끝나며, 이 사진은 처리하지 않는다.

출력

사진에는 나타난 순서대로 1,2,3,…1, 2, 3, \dots의 번호를 붙인다.

kk번째 사진에 대해 먼저 Throw k를 한 줄에 출력하고, 다음 줄에 그 사진에 있는 각 주사위의 눈의 개수를 증가하는 순서로 정렬하여 한 칸 공백으로 구분해 출력한다.

연속한 두 사진의 출력 사이에는 빈 줄을 하나 넣는다. 마지막 사진 뒤에는 빈 줄을 넣지 않는다.

예제1

  1. 예제 1

    입력
    30 15
    ..............................
    ..............................
    ...............*..............
    ...*****......****............
    ...*X***.....**X***...........
    ...*****....***X**............
    ...***X*.....****.............
    ...*****.......*..............
    ..............................
    ........***........******.....
    .......**X****.....*X**X*.....
    ......*******......******.....
    .....****X**.......*X**X*.....
    ........***........******.....
    ..............................
    0 0
    
    예상 출력
    Throw 1
    1 2 2 4