20056 마법사 상어와 파이어볼

🥇 20056 마법사 상어와 파이어볼

문제

마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.

• 모든 파이어볼이 자신의 방향 $d_i$
• 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
  • 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
  • 파이어볼은 4개의 파이어볼로 나누어진다.
  • 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
    질량은 $⌊(합쳐진 파이어볼 질량의 합)/5⌋$이다.
    속력은 $⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋$이다.
    합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
• 질량이 0인 파이어볼은 소멸되어 없어진다.

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.

입력

첫째 줄에 N, M, K가 주어진다.

둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 $r_i, c_i, m_i, s_i, d_i$

서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.

출력

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.

분석

삼성 기출 문제라고 한다. 로직자체는 어렵지 않은데 짜잘짜잘하게 꼼꼼히 챙겨야 할 것이 많다..다른 사람들은 이런 실수 안하겠지만, 나는 s랑 d를 거꾸로 받아서 풀어서 이 것 찾는데 시간을 엄청 썼고, 합쳐지는 파이어볼 방향 체크하는데에도 단순하게 짝수 + 짝수, 홀수 + 홀수인 경우만 신경을 써서 짝수 + 홀수 + 홀수 + 짝수가 들어오는 경우에도 합은 짝수가 된다는 걸 생각하지 못해서... 여태껏 푼 문제중 시간을 가장 많이 쓴 문제다ㅠㅠ
이 문제는 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 이 부분이 중요하다. 순환 큐 같은 구조이기 때문에, 범위를 체크할 필요없이 % N으로 정해진 방향대로 이동하도록 해주면 된다.
아래 코드는 기존 x, y 좌표에서 방향 d로 s만큼 이동하되, 행렬의 가로, 세로 크기 내에서 이동할 수있도록 하는 코드이다.

소스 코드

import sys
import math
from collections import deque
input = sys.stdin.readline

# 파이어볼 방향
move = {
    0: (-1, 0), 1: (-1, 1),
    2: (0, 1), 3: (1, 1),
    4: (1, 0), 5: (1, -1),
    6: (0, -1), 7: (-1, -1)
}

def moving(q):
    while q:
        x, y, m, s, d = q.popleft()
        nx, ny = (x + move[d][0] * s) % N, (y + move[d][1] * s) % N
        board[x][y].remove([m, s, d])
        board[nx][ny].append([m, s, d])

    for i in range(N):
        for j in range(N):
            if len(board[i][j]) > 1:
                # 파이어볼을 하나로 합침
                tmp = [0, 0] # m s
                length = len(board[i][j])
                odd = even = 0
                for k in range(length):
                    tmp[0] += board[i][j][k][0]
                    tmp[1] += board[i][j][k][1]
                    if board[i][j][k][2] % 2:
                        odd += 1
                    else:
                        even += 1

                board[i][j] = list()
                # 파이어볼은 4개의 파이어볼로 나누어짐
                mass = math.floor(tmp[0] / 5)
                speed = math.floor(tmp[1] / length)
                if mass:
                    if odd == length or even == length:
                        for D in [0, 2, 4, 6]:
                            board[i][j].append([mass, speed, D])
                            fireballs.append([i, j, mass, speed, D])
                    else:
                        for D in [1, 3, 5, 7]:
                            board[i][j].append([mass, speed, D])
                            fireballs.append([i, j, mass, speed, D])

            if len(board[i][j]) == 1: # i, j, m, s, d
                fireballs.append([i, j, board[i][j][0][0], board[i][j][0][1], board[i][j][0][2]])


N, M, K = map(int, input().split())
board = [[[] for _ in range(N)] for _ in range(N)]

fireballs = deque()
for _ in range(M):
    r, c, m, s, d = map(int, input().split())
    fireballs.append([r-1, c-1, m, s, d])
    board[r-1][c-1].append([m, s, d])

for _ in range(K):
    moving(fireballs)

total = 0
while fireballs:
    _, _, m, _, _ = fireballs.pop()
    total += m
print(total)