마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.
마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.
첫째 줄에 N, M, K가 주어진다.
둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 로 이루어져 있다.
서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.
마법사 상어가 이동을 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)