[BOJ]20056 마법사 상어와 파이어볼(Python) - 삼성SW역량테스트 기출

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

문제 요약

• 명령횟수만큼 주어진 방향, 속력으로 파이볼이 이동
• 한명령이 끝나고 겹쳐있는 파이어볼은 합쳐서 4개로 분할
  - 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
  - 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
  - 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
• 1행과 N행, 1열과 N열은 연결되어 있다 -> 즉, 경계 벗어나는 거 없이 1행 넘어가면 N행으로, N행 넘어가면 1행으로

# 22056 마법사 상어와 파이어볼 [삼성SW역량테스트 기출- 구현] 골드5 - 김수민
from collections import deque
N, M, K = map(int, input().split())
Q = deque(); cnt = 0
# 방향이동
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
dx = [0, 1, 1, 1, 0, -1, -1, -1]
for i in range(M):
    y, x, m, s, d = map(int, input().split())
    Q.append((y - 1, x - 1, m, s, d))

anw = 0
while cnt < K:
    bomblist = deque() # 합쳐질 애들 좌표 후보
    arr = [[[] for _ in range(N)] for _ in range(N)]
    visit = [[1] * N for _ in range(N)]
    hubo = [] # 합쳐지는 애들 말고 이동한 파이어볼들
    while Q:
        y, x, m, s, d = Q.popleft()
        ny = y + dy[d] * s; nx = x + dx[d] * s
        # 방향 조정(경계 넘어가면)
        if ny >= N:
            ny = ny % N
        elif ny < 0:
            while ny < 0:
                ny = N + ny
        if nx >= N:
            nx = nx % N
        elif nx < 0:
            while nx < 0:
                nx = N + nx
        # 이미 담겨져있으면(합쳐야 됨)
        if arr[ny][nx]:
            yy, xx, mm, ss, dd = arr[ny][nx].pop()
            mm += m; ss += s
            # 짝수, 홀수 방향이 섞여 있으면
            if (dd % 2 and d % 2 == 0) or (dd % 2==0 and d % 2 == 1): 
                dd = -1
            arr[ny][nx].append((yy,xx,mm,ss,dd))
            visit[ny][nx] += 1
            # 합쳐질 애들에 이미 포함돼있으면 통과
            if visit[ny][nx] <= 2:
                bomblist.append((ny, nx))
        else:
            hubo.append((ny, nx, m, s, d))
            arr[ny][nx].append((ny, nx, m, s, d))
    # 합쳐질 애들에 포함 안됐고 후보이면
    for idx in range(len(hubo)):
        y, x, m, s, d = hubo[idx]
        if visit[y][x] == 1:
            Q.append((y, x, m, s, d))
    # 합칠 애들
    for idx in range(len(bomblist)):
        r, c = bomblist.popleft()
        y, x, totm, tots, d = arr[r][c].pop()
        # 질량이 0이 되면 소멸
        if totm //5 == 0:
            continue
        if d != -1:
            for p in range(4):
                Q.append((r, c, totm//5, tots//visit[r][c], p * 2))
        else:
            for p in range(4):
                Q.append((r, c, totm//5, tots//visit[r][c], p * 2 + 1))
    cnt += 1

anw = 0
for i in range(len(Q)):
    y, x, m, s, d = Q[i]
    anw += m

print(anw)