[Python] 백준 21610 마법사 상어와 비바라기

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

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
   • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
   • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

# 21610 마법사 상어와 비바라기

move_dir = [[0, 0], [0, -1], [-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1]]
cross_rc = [[-1, -1], [-1, 1], [1, 1], [1, -1]]

N, M = map(int, input().split())
clouds = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
d = list()
s = list()
for _ in range(M):
    dd, ss = map(int, input().split())
    d.append(dd)
    s.append(ss)
    
rain = list()
rain.extend([[N, 1], [N, 2], [N - 1, 1], [N - 1, 2]])

for _ in range(M):
    cur_d = d.pop(0)
    cur_s = s.pop(0)
    direction_r, direction_c = move_dir[cur_d]
    # 모든 구름이 di 방향으로 si칸 이동한다.
    new_rain = list()
    for rain_r, rain_c in rain:
        rain_r += cur_s * direction_r
        rain_c += cur_s * direction_c
        while rain_r > N:
            rain_r -= N
        while rain_r <= 0:
            rain_r += N
        while rain_c > N:
            rain_c -= N
        while rain_c <= 0:
            rain_c += N
        new_rain.append([rain_r, rain_c])
    
    rain = list()
    # 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
    for rain_r, rain_c in new_rain:
        clouds[rain_r][rain_c] += 1
        
    # 구름이 모두 사라진다. (== 상단에서 new_rain 초기화)
    visited = [[0] * (N + 1) for _ in range(N + 1)]
    for rain_r, rain_c in new_rain:
        visited[rain_r][rain_c] = 1
    
    # 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다.
    for rain_r, rain_c in new_rain:
        for i in range(4):
            cr = rain_r + cross_rc[i][0]
            cc = rain_c + cross_rc[i][1]
            if 1 <= cr and cr <= N and 1 <= cc and cc <= N and clouds[cr][cc] > 0:
                clouds[rain_r][rain_c] += 1
    
    # 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다.
    # 앞에서 구름이 사라진 칸이 아니어야 한다.
    for r in range(1, N + 1):
        for c in range(1, N + 1):
            if visited[r][c] == 0 and clouds[r][c] >= 2:
                rain.append([r, c])
                clouds[r][c] -= 2

ans = 0
for cl in clouds:
    ans += sum(cl)

print(ans)