문제종류
구현, dx dy technique
풀이시간
설계 10분, 구현 40분
풀이방법
위 문제는 크게 두단계로 이뤄진다
1. 먼지의 확산
2. 돌풍에 의해 날아가는 먼지 (반시계, 시계)
문제 요구사항을 잘 읽고 그대로 구현하면 되는 문제다
주의해야 할 것이 먼지의 확산 단계에서 돌풍이 있는 곳은 전파하면 안된다.
코드
from copy import deepcopy
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
def in_range(x, y, n, m):
return 0 <= x < n and 0 <= y < m
def main():
n, m, t = map(int, input().split())
ans = 0
arr = [list(map(int, input().split())) for _ in range(n)]
uwx, dwx = -1, -1
for i in range(n):
for j in range(m):
if arr[i][j] == -1:
if uwx == -1:
uwx = i
else:
dwx = i
for _ in range(t):
# 확산 (x, y, diff)
spread_list = []
for r in range(n):
for c in range(m):
if arr[r][c] == -1:
continue
spread_sum = 0
for ddx, ddy in zip(dx, dy):
nr = r + ddx
nc = c + ddy
if in_range(nr, nc, n, m) and arr[nr][nc] != -1:
spread_list.append((nr, nc, arr[r][c] // 5))
spread_sum += arr[r][c] // 5
spread_list.append((r, c, -spread_sum))
for x, y, diff in spread_list:
arr[x][y] += diff
# 확산 end
# 윗 돌풍 (2, n-1) (1, n-2)
rtmp = deepcopy(arr)
rtmp[uwx][1] = 0
rtmp[uwx][2:] = arr[uwx][1:m - 1]
for nux in range(uwx - 1, -1, -1):
rtmp[nux][m - 1] = arr[nux + 1][m - 1]
rtmp[0][:m - 1] = arr[0][1:]
for nux in range(1, uwx):
rtmp[nux][0] = arr[nux - 1][0]
rtmp[dwx][1] = 0
rtmp[dwx][2:] = arr[dwx][1:m - 1]
for nux in range(dwx + 1, n):
rtmp[nux][m - 1] = arr[nux - 1][m - 1]
rtmp[n - 1][:m - 1] = arr[n - 1][1:]
for nux in range(n - 2, dwx, -1):
rtmp[nux][0] = arr[nux + 1][0]
arr = rtmp
# 정답 구하기
for r in range(n):
for c in range(m):
if arr[r][c] != -1:
ans += arr[r][c]
print(ans)
main()
'알고리즘 > 코드트리' 카테고리의 다른 글
[코드트리] - 팩맨 (0) | 2023.09.27 |
---|---|
[코드트리] - 나무박멸 (1) | 2023.09.26 |
[코드트리] - 포탑부수기 (1) | 2023.09.25 |
[코드트리] - 싸움땅 (0) | 2023.09.23 |
[코드트리] - 격자 숫자 놀이 (0) | 2023.09.22 |