무요 무요

면접 대비

시간 제한2초메모리 제한512 MB

요약

너비 10인 격자에서 같은 색으로 연결된 K개 이상의 무리를 찾아 동시에 지우고 중력을 적용하기를 반복한 뒤 최종 보드를 출력한다.

난이도: 보통10점 중 4점
유형: DFS, 시뮬레이션, 구현, 그래프
정답자: 아직 제출이 없습니다

문제

농부 존의 농장에 있는 소들은 할 일이 많지 않아서(정확히는 발굽이 남아돌아서) 종종 비디오 게임을 하며 시간을 보낸다. 소들이 가장 좋아하는 게임 중 하나는 인간들의 인기 게임인 뿌요뿌요를 바탕으로 한 것으로, 소 버전의 이름은 당연히 무요 무요다.

무요 무요는 세로로 $N$ 칸( $1 \leq N \leq 100$ ), 가로로 10칸인 길쭉한 격자에서 진행된다. $N = 6$ 인 예시는 다음과 같다.

각 칸은 비어 있거나(0으로 표시), 아홉 가지 색 중 하나의 건초더미(문자 1..9로 표시)가 들어 있다. 중력 때문에 건초더미는 아래로 떨어지므로, 건초더미 아래에 0인 칸은 존재하지 않는다.

두 칸이 가로 또는 세로로 맞닿아 있고 0이 아닌 같은 색이면, 두 칸은 같은 연결 영역에 속한다. 크기가 $K$ 이상인 연결 영역이 존재하면, 그 영역의 건초더미는 모두 사라져 0이 된다. 그런 연결 영역이 동시에 여러 개 존재하면 모두 동시에 사라진다. 그 후 중력으로 인해 건초더미가 아래로 떨어져 0이 된 칸 일부를 채울 수 있다. 그 결과에서 다시 크기가 $K$ 이상인 연결 영역이 생길 수 있다. 그런 영역이 있으면 그것들도 사라지고(여러 개면 동시에), 다시 중력이 남은 칸을 아래로 끌어내리며, 크기가 $K$ 이상인 연결 영역이 더 이상 존재하지 않을 때까지 이 과정이 반복된다.

무요 무요 판의 상태가 주어졌을 때, 이 과정이 모두 끝난 뒤의 최종 판 상태를 출력하라.

입력

첫째 줄에 $N$ 과 $K$ 가 주어진다( $1 \leq K \leq 10N$ ). 나머지 $N$ 개의 줄은 판의 초기 상태를 나타낸다.

출력

최종 판 상태를 나타내는 $N$ 개의 줄을 출력하라.

힌트

위 예시에서 $K = 3$ 이면 색 1인 연결 영역과 색 2인 연결 영역이 각각 크기 $K$ 이상이다. 이 둘을 동시에 제거하면 판은 잠시 다음과 같이 된다.

그 후 중력이 작용하여 건초더미가 다음과 같이 떨어진다.

다시 크기가 $K$ 이상인 영역(색 3)이 있다. 이것을 제거하면 최종 판 상태가 된다.

예제1

예제 1

입력

예상 출력