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

문제

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

접근

완전 탐색을 이용한 구현 문제

1) 맵을 4차원 리스트로 지정한다. 4차원 리스트로 지정하는 이유는 맵의 원소에 질량, 속력, 방향을 저장하기 위함이다.

2) 맵을 전부 뒤지면서 파이어볼을 이동시킨다. 이 때 한 곳에 파이어볼이 몰려있을 수가 있는데, 이 때는 pop을 이용해 요소를 삭제시켜준다.

3) 전부 이동 후 맵을 다시 뒤지면서 합쳐진 파이어볼을 찾는다.

4) 합쳐진 파이어볼을 찾고 현재 방향과 다르면 is_same_direct라는 플래그를 False로 바꿔준다.

5) is_same_direct의 값에 따라 방향을 다르게 지정하고 한 곳에 4개의 파이어볼을 넣어준다. 이 때 질량이 0일 경우 넣지 않는다.

Code

import sys
from collections import defaultdict, deque

n, m, k = map(int, sys.stdin.readline().split())
fireballs = deque()
dirs = {0: (-1, 0), 1: (-1, 1), 2: (0, 1), 3: (1, 1), 4: (1, 0), 5: (1, -1), 6: (0, -1), 7: (-1, -1)}
answer = 0
maps = [[[] for _ in range(n)] for _ in range(n)]

for _ in range(m):
    y, x, w, s, d = map(int, sys.stdin.readline().split())
    maps[y - 1][x - 1].append([w, s, d])  # 0 : 질량, 1 : 속력, 2 : 방향

# 1. 파이어볼 이동
fireballs = []
while k:
    for y in range(n):
        for x in range(n):
            if maps[y][x]:
                while maps[y][x]:
                    w, s, d = maps[y][x].pop()
                    fireballs.append([y, x, w, s, d])

    while fireballs:
        y, x, w, s, d = fireballs.pop()
        cy, cx = (y + dirs[d][0] * s) % n, (x + dirs[d][1] * s) % n
        maps[cy][cx].append([w, s, d])

    # 2. 파이어볼 4분할
    for y in range(n):
        for x in range(n):
            if len(maps[y][x]) > 1:
                is_same_direct = True
                curr_direct = -1
                total_w, total_s = 0, 0
                cnt = len(maps[y][x])
                while maps[y][x]:
                    w, s, d = maps[y][x].pop()
                    total_w += w
                    total_s += s
                    if curr_direct == -1:
                        curr_direct = d % 2
                    elif curr_direct != d % 2:
                        is_same_direct = False

                divide_w, divide_s = total_w // 5, total_s // cnt
                if divide_w:
                    if is_same_direct:
                        for i in range(0, 7, 2):
                            maps[y][x].append([divide_w, divide_s, i])
                    else:
                        for i in range(1, 8, 2):
                            maps[y][x].append([divide_w, divide_s, i])
    k -= 1

for y in range(n):
    for x in range(n):
        for k in range(len(maps[y][x])):
            answer += maps[y][x][k][0]
print(answer)

여담

처음에는 자료구조 4개를 만들기 싫어서 이상한 구현을 하다가 결국 4차원 배열을 만들어서 풀었다. 자료구조 4개나 4차원 배열이나 비슷한 방법 같긴한데.. 이런 시뮬레이션 문제는 꾀를 부리지 않고 시간복잡도와 공간복잡도가 여유로우면 이렇게 푸는 게 제일 좋은 방법인 듯 하다.