떨어지는 사과
면접 대비시간 제한5초메모리 제한512 MB
장애물은 고정된 격자에서 사과가 더 이상 움직이지 않을 때까지 아래로 떨어지게 한 뒤 최종 격자를 출력한다.
문제
R행 C열 직사각형 격자가 있다. 각 칸은 비어 있거나, 사과가 놓여 있거나, 장애물이 놓여 있다. 빈 칸은 ., 사과는 a, 장애물은 #으로 나타낸다.
다음 규칙에 따라 중력을 적용한다.
- 장애물은 움직이지 않는다.
- 사과 바로 아래 칸이 비어 있으면 그 사과는 아래 칸으로 내려간다.
더 이상 내려갈 사과가 없을 때까지 규칙을 적용한 뒤, 격자의 마지막 상태를 출력한다. 규칙을 한 칸씩 반복해서 적용하는 방법은 큰 입력에서 시간이 부족하다.
입력
첫 줄에 격자의 행 수 R과 열 수 C가 주어진다 (, ).
이어지는 R개의 줄에는 격자의 각 행이 위에서 아래 순서로 주어진다. 각 줄은 ., a, # 중 하나인 문자 C개로 이루어진다.
출력
마지막 상태의 격자를 R개의 줄에 출력한다.