10703 유성

문제

https://www.acmicpc.net/problem/10703

10703번: 유성

 

접근

• 각각의 유성 조각에 대해 떨어질 수 있는 높이의 최솟값을 구한 후, 모든 유성에 대해 구한 최솟값 만큼 아래로 떨어트린다.
• 아래와 같이 유성 조각 아래에 땅이 있고 또 그 아래에 유성 조각이 있는 경우 또한 처리해줘야 한다.

.	.	.	.	.	.	.	.	.
.	.	X	X	X	X	.	.	.
.	.	X	.	.	.	.	.	.
.	.	X	#	#	#	#	#	#
.	.	X	.	.	.	.	.	#
.	.	X	X	X	X	.	.	#
.	.	.	.	.	.	.	.	#
#	#	.	.	.	.	.	#	#
#	#	#	#	#	#	#	#	#

 

풀이

• 유성 조각을 발견할 때마다 cnt 값을 0으로 설정하고, 아래가 공기일 경우 +1, 땅을 만날 경우 떨어질 수 있는 높이의 최솟값을 계산해서 전체 최솟값을 갱신한다.
• 만약 유성이 존재하지 않는 경우는 cnt를 -1로 표시해서 높이 계산에서 제외한다.
• 높이의 최솟값을 구한 후, 각 유성 조각마다 아래로 이동시킨 후 출력한다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
picture = [list(input().rstrip()) for _ in range(n)]

min_cnt = n
ans = [["."] * m for _ in range(n)]
for j in range(m):
    cnt = -1
    tmp = []
    for i in range(n):
        if picture[i][j] == "X":
            cnt = 0
        elif picture[i][j] == "#":
            ans[i][j] = "#"
            if cnt != -1:
                min_cnt = min(min_cnt, cnt)
        else:
            if cnt != -1:
                cnt += 1


for j in range(m):
    for i in range(n):
        if picture[i][j] == "X":
            ans[i + min_cnt][j] = picture[i][j]
            picture[i][j] = "."

for row in ans:
    print("".join(row))