마법사 상어와 파이어볼 [백준 20056번]

문제

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

20056번: 마법사 상어와 파이어볼

 

내 풀이

 

grid를 []로 구성된 2차원 배열로 선언하였다. (따지고 보면 모양이 독특한 3차원 배열이다. 길이가 가변적인 3차원 배열..?)

 

먼저 파이어볼을 이동시키는 것을 구현하였다.

하나의 좌표에 여러 개의 파이어볼이 있을 수 있으므로, 여러 개의 파이어볼이 있는지 파악하고 전부 이동시켜주는 것이 중요하다.

 

이동시킨 후, 2개 이상의 파이어볼이 있는 좌표에서 파이어볼들을 하나로 합친 후 4개로 나누어지는 것을 구현하였다.

여기서는 기존에 있던 파이어볼을 제거해야 하므로 pop(0)을 사용하였다.

그리고 방향이 모두 홀수 또는 모두 짝수인지에 따라 4개로 나눠진 파이어볼들의 d가 다르다. 이것을 odd 변수를 사용하여 구하였다.

 

마지막에 남아있는 파이어볼의 전체 질량을 구하면 된다.

 

import copy

N, M, K = map(int, input().strip().split())
grid = [[[] for i in range(N)] for j in range(N)]
dr, dc = [-1, -1, 0, 1, 1, 1, 0, -1], [0, 1, 1, 1, 0, -1, -1, -1]
for i in range(M):
    r, c, m, s, d = map(int, input().strip().split())
    grid[r-1][c-1].append((m, s, d))

for k in range(K):
    new_grid = [[[] for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if grid[i][j]:
                for g in grid[i][j]:
                    m, s, d = g
                    nr, nc = (i + dr[d] * s) % N, (j + dc[d] * s) % N
                    new_grid[nr][nc].append((m, s, d))
    grid = copy.deepcopy(new_grid)
    for i in range(N):
        for j in range(N):
            len_grid = len(grid[i][j])
            if len_grid >= 2:
                sum_m, sum_s, odd = 0, 0, 0
                while grid[i][j]:
                    m, s, d = grid[i][j].pop(0)
                    sum_m += m
                    sum_s += s
                    if d % 2: odd += 1
                new_m = sum_m // 5
                new_s = sum_s // len_grid
                if odd == 0 or odd == len_grid: new_d = [0, 2, 4, 6]
                else: new_d = [1, 3, 5, 7]
                if new_m:
                    for d in new_d:
                        grid[i][j].append((new_m, new_s, d))
total = 0
for i in range(N):
    for j in range(N):
        if grid[i][j]:
            for info in grid[i][j]:
                total += info[0]
print(total)

 

총평

시뮬레이션 힘들다...

문제를 잘 읽자.