[백준 20056] 마법사 상어와 파이어볼(Python)

최근에 화이자 1차 접종을 맞았다.

1. 아이디어

불에 관한 정보를 배열에 저장하지 않고 딕셔너리에 저장했다. 딕셔너리의 key는 불이 있는 좌표고 value는 tuple(질량, 속력, 방향)을 저장하는 리스트이다. value의 타입이 리스트인 이유는 하나의 좌표에서 다수의 불이 존재할 수 있기 때문이다.

각 불의 좌표(key)에 대해, value에 있는 모든 정보를 각 정보에 의해 이동된 불의 좌표(key)에대한 value에 저장한다. 저장하는 과정은 사본 딕셔너리를 만들어서, 불의 이동 결과를 사본 딕셔너리에 저장했다. 모든 이동이 끝났으면, 사본 딕셔너리의 정보를 원본 딕셔너리에 반영했다.

불의 이동이 반영된 딕셔너리를 활용하여, 불을 합치고 나누는 과정을 구하면된다. 문제에 제시된 조건대로 구현하면 된다.

2. 코드

n, m, k = map(int, input().split())
fires = {}
v = ((-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1))

for _ in range(m):
    y, x, m, s, d = map(int, input().split())
    y, x = y-1, x-1
    if (y, x) in fires.keys(): fires[(y,x)].append((m, s, d))
    else: fires[(y,x)] = [(m,s,d)]

def move_fires():
    _dict = {}
    for y, x in fires.keys():
        while fires[(y,x)]:
            m, s, d = fires[(y,x)].pop()
            ny = (y + v[d][0] * s) % n
            nx = (x + v[d][1] * s) % n
            if (ny,nx) not in _dict.keys(): _dict[(ny,nx)] = [(m,s,d)]
            else: _dict[(ny,nx)].append((m,s,d))
    
    for y, x in _dict.keys():
        while _dict[(y,x)]:
            m, s, d = _dict[(y,x)].pop()
            if (y, x) not in fires.keys(): fires[(y,x)] = [(m,s,d)]
            else: fires[(y,x)].append((m,s,d))

def divide_fires():
    for y, x in fires.keys():
        total_m, total_s, odds = [0]*3
        size = len(fires[(y,x)])
        if size == 1: continue

        while fires[(y,x)]:
            m, s, d = fires[(y,x)].pop()
            total_m += m
            total_s += s
            if d % 2 == 1: odds += 1
        
        total_m //= 5
        if not total_m: continue
        total_s //= size
        k = []
        if odds == 0 or odds == size: k = [i for i in range(0, 8, 2)]       
        else: k = [i for i in range(1, 9, 2)]
        for i in k: fires[(y,x)].append((total_m, total_s, i))
 
while k:
    move_fires()
    divide_fires()
    k -= 1

answer = 0
for y, x in fires.keys():
    while fires[(y,x)]:
        m, _, _ = fires[(y,x)].pop()
        answer += m

print(answer)