문제 링크

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

문제 설명

• 파이어볼들의 위치, 질량, 속도, 방향이 주어진다
• 이동을 K번 반복
• 파이어볼끼리 만나면 합쳐졌다가 흩어짐
• 마지막으로 남아있는 파이어볼들의 질량의 합 출력

풀이

• 이동, 만나는 경우를 나누어서 구현했다
• 이동 후 board를 따로 만들어서 모두 이동한 후 갱신해줬다

후기

• 어떻게 구현할지 생각하는데 살짝 오래 걸렸다
• 만났을 경우에만 흩어져야 하는데 빼먹어서 디버깅하느라 살짝 헤맸다
• 채점해보니 시간이 굉장히 많이 걸린다
• python3은 시간초과가 났다
• 딕셔너리로 파이어볼이 존재하는 좌표만 계산할 수도 있을 것 같고
• 이동할 때 한 칸씩 움직이는게 아니라 한 번에 계산할 수 있을 것 같다

코드

def move():
    global board
    new_board = [[[] for _ in range(n+1)] for _ in range(n+1)]
    for y in range(1, n+1):
        for x in range(1, n+1):
            for m, s, d in board[y][x]:
                ny, nx = get_next(y, x, s, d)
                new_board[ny][nx].append([m, s, d])
    board = new_board


def get_next(y, x, s, d):
    for _ in range(s):
        dy, dx = dirs[d]
        y = (y + dy - 1) % n + 1
        x = (x + dx - 1) % n + 1
    return y, x


def change():
    for y in range(1, n+1):
        for x in range(1, n+1):
            if len(board[y][x]) < 2:
                continue
            new_fires = []
            sum_m, sum_s = 0, 0
            all_odd, all_even = True, True
            for m, s, d in board[y][x]:
                sum_m += m
                sum_s += s
                if d % 2 == 1:
                    all_even = False
                else:
                    all_odd = False
            tmp = 1
            if all_even or all_odd:
                tmp = 0
            for i in range(4):
                if sum_m // 5:
                    new_fires.append([sum_m//5, sum_s//len(board[y][x]), 2*i+tmp])
            board[y][x] = new_fires


def get_sum():
    summ = 0
    for y in range(1, n+1):
        for x in range(1, n+1):
            for m, s, d in board[y][x]:
                summ += m
    return summ


# init
import sys
read = sys.stdin.readline
n, m, k = map(int, read().split())
board = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    r,c,m,s,d = map(int, read().split())
    board[r][c].append([m,s,d])
dirs = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]

# start
for _ in range(k):
    move()
    change()
print(get_sum())