문제
https://www.acmicpc.net/problem/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))
'Python > Coding Test' 카테고리의 다른 글
20182 골목 대장 호석 - 효율성 1 (0) | 2022.02.25 |
---|---|
21277 짠돌이 호석 (0) | 2022.02.24 |
13168 내일로 여행 (0) | 2022.02.23 |
1421 나무꾼 이다솜 (0) | 2022.02.23 |
2563 전깃줄 (0) | 2022.02.22 |