20056. 마법사 상어와 파이어볼 문제 바로가기
해결 방법
주요 과정
모든 파이어볼을 이동한다.
격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
tip) 이때 다음과 같은 문제 조건이 있는 데 이러한 경우 다음의 연산으로 만족시킬 수 있다.
1 2
x = (x + N) % N y = (y + N) % N
다음의 연산을 통해 0번 인덱스에서 왼쪽으로 1칸 이동할 때 마지막 인덱스로 이동하는 것을 확인할 수 있다.
2개 이상의 파이어볼이 있는 칸을 찾아 4개의 파이어볼로 만든다.
위의 1, 2번 과정을 K번 동안 반복한 뒤 board에 남아있는 파이어볼의 질량의 합을 구한다.
구현한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
from copy import deepcopy
N, M, K = map(int, input().split())
board = [[[] for _ in range(N)] for _ in range(N)]
# board에 상어가 있는 경우 [m, s, d] 로 저장하기
for _ in range(M):
r, c, m, s, d = map(int, input().split())
if m != 0:
board[r - 1][c - 1].append([m, s, d])
dirs = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]
for _ in range(K):
n_board = [[[] for _ in range(N)] for _ in range(N)]
# 1. 모든 파이어볼이 이동한다.
for y in range(N):
for x in range(N):
if board[y][x] != []:
for b in range(len(board[y][x])):
nm, ns, nd = board[y][x][b]
ny, nx = y + dirs[nd][0] * ns, x + dirs[nd][1] * ns
nx = (nx + N) % N
ny = (ny + N) % N
n_board[ny][nx].append([nm, ns, nd])
# 2. 2개 이상의 파이어볼이 있는 칸을 찾아 4개의 파이어볼을 만든다.
for y2 in range(N):
for x2 in range(N):
if len(n_board[y2][x2]) > 1:
cm, cs, cd = 0, 0, []
cnt = len(n_board[y2][x2])
for c in range(cnt):
cm += n_board[y2][x2][c][0]
cs += n_board[y2][x2][c][1]
cd.append(n_board[y2][x2][c][2] % 2)
cm = int(cm / 5)
cs = int(cs / cnt)
n_board[y2][x2] = []
if cm != 0: # 질량이 0 인 경우 소멸하는 조건 고려
if sum(cd) == 0 or sum(cd) == cnt: # 합쳐지는 파이어볼 방향이 모두 홀수거나 짝수인 경우
for i in range(4):
n_board[y2][x2].append([cm, cs, i * 2])
else:
for j in range(4):
n_board[y2][x2].append([cm, cs, j * 2 + 1])
board = deepcopy(n_board)
# 남아있는 파이어볼 질량의 합 구하기
sum_m = 0
for y in range(N):
for x in range(N):
if board[y][x] != []:
for b in range(len(board[y][x])):
sum_m += board[y][x][b][0]
print(sum_m)