[Python] 20056. 마법사 상어와 파이어볼

www.acmicpc.net/problem/20056

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

---

 

Point

• 첫 입력에서 서로 다른 두 파이어볼 위치가 같은 경우는 없음
• 파이어볼 질량이 0 이 되면 소멸

 

 

 

Tip

• 2차원 리스트 배열을 선언하여 이동이 끝난 뒤 파이어볼 합치기/분열을 연산
• 파이어볼의 방향을 연산할 때, 총합이 짝수/홀수냐로 모두 짝수/홀수인지 아닌지를 판별하면 안된다.
  짝짝홀홀일 때 총합은 짝수이기 때문이다. 

 

메모리 (제한: 512MB)

138280 KB

시간 (제한: 1초)

488 ms

결과

100%

 

import sys
input = sys.stdin.readline

n,m,k = map(int, input().split())
fireballs = []
for _ in range(m):
    _r,_c,_m,_s,_d = map(int, input().split())
    fireballs.append([_r-1,_c-1,_m,_s,_d])
dydx = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]

for _ in range(k):
    MAP = [[[] for _ in range(n)] for _ in range(n)]

    # 모든 파이어볼 이동
    while fireballs:
        cy,cx,cm,cs,cd = fireballs.pop(0)
        ny = (cy + cs*dydx[cd][0])%n
        nx = (cx + cs*dydx[cd][1])%n
        MAP[ny][nx].append([cm,cs,cd])

    # 이동이 끝난 뒤 2개 이상칸에서는 합치고 분열
    tmp = []
    for r in range(n):
        for c in range(n):
            if MAP[r][c]:
                if len(MAP[r][c]) == 1:
                    tmp.append([r,c]+MAP[r][c][0])
                    # answer += MAP[r][c][0][0]
                else:
                    cnt = len(MAP[r][c])
                    sum_m = 0
                    sum_s = 0
                    cnt_odd = 0
                    cnt_even = 0
                    while MAP[r][c]:
                        _m,_s,_d = MAP[r][c].pop(0)
                        sum_m += _m
                        sum_s += _s
                        if _d % 2 == 1:
                            cnt_odd += 1
                        else:
                            cnt_even += 1

                    # 짝 짝 홀 홀 이어도 합이 양수가 나올 수 있음
                    # 방향이 모두 양수/음수인지 판별
                    flag = False
                    if cnt_odd == cnt or cnt_even == cnt:
                        flag = True

                    if sum_m//5 > 0:
                        if flag:
                            for nd in [0,2,4,6]:
                                tmp.append([r,c,sum_m//5,sum_s//cnt,nd])
                        elif not flag:
                            for nd in [1,3,5,7]:
                                tmp.append([r,c,sum_m//5,sum_s//cnt,nd])
                        # answer += (sum_m//5)*4
                    # 질량이 0 인 파이어볼은 소멸
                    else:
                        continue
    fireballs = tmp

answer = sum([f[2] for f in fireballs])
print(answer)

 

문제를 푸는데 도움이 된 테스트 케이스