백준 20056 마법사 상어와 파이어볼 (파이썬)

www.acmicpc.net/problem/20056

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

1. 지도 a와 파이어볼이 있는 좌표를 저장할 q를 만든다

   a에는 파이어볼이 있는 좌표에 [질량 m, 속력 s, 방향 d]를 저장한다

2. 현재 큐에 있는 좌표만 불러오기 위해서 len(q)만큼만 popleft 한다

   a에는 파이어볼이 여러개 있을 수 있기 때문에 마찬가지로 현재 좌표안에 있는 만큼만 popleft한다

3. a에서 n-1과 0번째 인덱스는 서로 이어져있으므로 다음 좌표는 (속력 * 방향 + 현재 좌표) % n 가 된다

   q에 다음 좌표를 append하고 temp에 다음 좌표와 파이어볼에 대한 정보들을 append한다

   temp는 다음 좌표가 저장된 파이어볼들이고 나중에 따로 이동해야 중복 여러번 이동하는 경우를 막을 수 있다

4. temp에 있는 파이어볼을 하나씩 불러와서 지도 a에 저장한다

5. len(a[x][y])가 1보다 크면 해당 좌표에 파이어볼이 겹치는 경우이므로 조건대로 처리해야 한다

   새로운 질량, 속력에 대한 변수 nm, ns를 만들고 방향의 홀짝여부를 판단하는 odd, even, flag를 만든다

6. 질량과 속력은 각각 nm, ns에 합쳐둔다

   해당 좌표에서 맨 처음 불러온 파이어볼의 방향이 짝수이면 even을 1로, 홀수면 odd를 1로 한다

   이후에 even이 1인데 속력이 홀수면 flag를 1로한다. (반대 경우도 마찬가지)

7. 문제의 조건대로 nm, ns를 갱신하고 a[i][j]를 초기화해서 nm이 0이면 파이어볼이 없어진걸로 처리한다

8. 질량이 0이 아니면 앞서만든 flag를 바탕으로 방향을 설정해주고 해당 좌표에 새로운 파이어볼 4개를 append한다

9. k만큼 반복이 끝나면 질량을 다 더하고 출력한다

from collections import deque
import sys

input = sys.stdin.readline
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

n, m, k = map(int, input().split())
q = deque()
a = [[deque() for _ in range(n)] for _ in range(n)]
for _ in range(m):
    r, c, m, s, d = map(int, input().split())
    a[r-1][c-1].append([m, s, d])
    q.append([r-1, c-1])

for _ in range(k):
    temp = []
    qlen = len(q)
    for _ in range(qlen):
        x, y = q.popleft()
        for _ in range(len(a[x][y])):
            m, s, d = a[x][y].popleft()
            nx = (s * dx[d] + x) % n
            ny = (s * dy[d] + y) % n
            q.append([nx, ny])
            temp.append([nx, ny, m, s, d])

    for x, y, m, s, d in temp:
        a[x][y].append([m, s, d])

    for i in range(n):
        for j in range(n):
            if len(a[i][j]) > 1:
                nm, ns, odd, even, flag = 0, 0, 0, 0, 0
                for idx, [m, s, d] in enumerate(a[i][j]):
                    nm += m
                    ns += s
                    if idx == 0:
                        if d % 2 == 0:
                            even = 1
                        else:
                            odd = 1
                    else:
                        if even == 1 and d % 2 == 1:
                            flag = 1
                        elif odd == 1 and d % 2 == 0:
                            flag = 1

                nm //= 5
                ns //= len(a[i][j])
                a[i][j] = deque()
                if nm != 0:
                    for idx in range(4):
                        nd = 2 * idx if flag == 0 else 2 * idx + 1
                        a[i][j].append([nm, ns, nd])

ans = 0
for i in range(n):
    for j in range(n):
        if a[i][j]:
            for m, s, d in a[i][j]:
                ans += m
print(ans)