5. [re] 마법사 상어와 비바라기

백준

1. 시뮬레이션

최적화 <튜플로 접근>

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
move = [tuple(map(int, input().split())) for _ in range(m)]

#←, ↖, ↑, ↗, →, ↘, ↓, ↙
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
cloud = [(n - 1, 0), (n - 1, 1), (n - 2, 0), (n - 2, 1)]

for i in range(m):
    d, s = move[i]
    d = d - 1
    temp = []
    for x, y in cloud:
        nx = (x + (dx[d] * s)) % n
        ny = (y + (dy[d] * s)) % n
        temp.append((nx, ny))


    for x, y in temp:
        board[x][y] += 1

    for x, y in temp:
        cnt = 0
        for dir in range(1, 8, 2):
            nx = x + dx[dir]
            ny = y + dy[dir]
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] != 0:
                cnt += 1
        if cnt > 0:
            board[x][y] += cnt

    cloud = []

    for k in range(n):
        for j in range(n):
            if board[k][j] >= 2 and (k, j) not in temp:
                cloud.append((k, j))
                board[k][j] -= 2


result = 0
for i in range(n):
    for j in range(n):
        if board[i][j] != 0:
            result += board[i][j]

print(result)

시간초과

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
move = [list(map(int, input().split())) for _ in range(m)]

#←, ↖, ↑, ↗, →, ↘, ↓, ↙
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
cloud = [[n - 1, 0], [n - 1, 1], [n - 2, 0], [n - 2, 1]]

for i in range(m):
    d, s = move[i]
    d = d - 1
    temp = []
    for x, y in cloud:
        nx = (x + (dx[d] * s)) % n
        ny = (y + (dy[d] * s)) % n
        temp.append([nx, ny])


    for x, y in temp:
        board[x][y] += 1

    for x, y in temp:
        cnt = 0
        for dir in range(1, 8, 2):
            nx = x + dx[dir]
            ny = y + dy[dir]
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] != 0:
                cnt += 1
        if cnt > 0:
            board[x][y] += cnt

    cloud = []

    for k in range(n):
        for j in range(n):
            if board[k][j] >= 2 and [k, j] not in temp:
                cloud.append([k, j])
                board[k][j] -= 2


result = 0
for i in range(n):
    for j in range(n):
        if board[i][j] != 0:
            result += board[i][j]

print(result)