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

<문제 링크>

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

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

<풀이 전략>

1. 특별한 알고리즘을 필요로 하지 않는 구현 문제이다.
2. 어떤 자료구조형을 어떻게 사용해서 파이어볼의 정보와 위치 등을 나타낼 것인가가 생각하기 좀 까다롭다
3. 구현해야할 요소는 크게 파이어볼의 이동 / 파이어볼의 병합과 분산이다.
4. 먼저 파이어볼의 이동이다.
   1. 파이어어볼의 이동은 리스트에 담은 파이어볼의 정보를 하나씩 꺼내서 빈 리스트를 원소로 가진 N x N 배열(리스트를 원소로 가지므로3차원 배열이다)에 표시해주었다.
   2. 1번 행과 N번 행이, 1번 열과 N번 열이 연결되어 있으므로 N으로 나눈 나머지로 좌표를 표시해야한다.
5. 파이어볼의 병합과 분산이다.
   1. 파이어볼의 이동에서 했던 거의 역순으로 이번에는 배열에서 파이어볼을 꺼내서 다시 리스트에 담아준다.
   2. N x N 배열에 원소가 2개 이상 있으면 문제에 주어진 조건대로 병합과 분산을 구현해 수행해준다.
   3. 1개일 경우에는 따로 할 게 없으므로 그대로 다시 리스트에 담아준다.
6. 위 과정을 K 번 수행하고 남아있는 파이어볼의 질량의 합을 구해주면 된다.
7. 개인적으로는 생각보다 구현이 까다롭고 신경 쓸 게 많아야 했던 문제였다.

<정답 코드>

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 220921 20056 마법사 상어와 파이어볼

# 정답코드

# N: 배열 크기, M: 파이어볼 개수, K: 이동 회수
N, M, K = map(int, input().split())

# fireball: 파이어볼 리스트
fireball = []
for _ in range(M):
    temp = list(map(int, input().split()))
    # 0_index로 저장
    temp[0] -= 1
    temp[1] -= 1
    fireball.append(temp)

# arr: 파이어볼이 위치하는 배열
arr = [[[] for _ in range(N)] for _ in range(N)]

# direction: 위치 정보
direction = {
    0 : (-1, 0),
    1 : (-1, 1),
    2 : (0, 1),
    3 : (1, 1),
    4 : (1, 0),
    5 : (1, -1),
    6 : (0, -1),
    7 : (-1, -1),
}


# move: 파이어볼의 이동
def move():

    # 리스트에서 파이어볼을 하나씩 꺼내서 배열에 이동 위치를 표시해준다.
    while fireball:
        fireball_info = fireball.pop()

        # 파이어볼 이동
        fireball_info[0] = (fireball_info[0] + (fireball_info[3] * direction[fireball_info[4]][0])) % N
        fireball_info[1] = (fireball_info[1] + (fireball_info[3] * direction[fireball_info[4]][1])) % N

        # 베열에 파이어볼 표시
        arr[fireball_info[0]][fireball_info[1]].append([fireball_info[2], fireball_info[3], fireball_info[4]])

    return 


# merge_split: 파이어볼이 합쳐졌다가 나뉘어지는 함수
def merge_split():
    for r in range(N):
        for c in range(N):

            # 배열의 동일한 위치에 파이어볼이 두 개 이상인 경우
            if len(arr[r][c]) > 1:

                # nm, ns: 나뉘어진 파이어볼의 질량과 속도
                nm = 0
                ns = 0
                # even, odd: 합쳐지는 파이어볼의 방향을 세는 변수
                even = 0
                odd = 0
                # cnt: 합쳐지는 파이어볼의 개수
                cnt = len(arr[r][c])

                while arr[r][c]:
                    # 파이어볼의 질량과 속도를 더해준다.
                    m, s, d = arr[r][c].pop()
                    nm += m
                    ns += s
                    # 파이어 볼의 방향을 세준다.
                    if d % 2:
                        odd += 1
                    else:
                        even += 1

                # 파이어볼의 질량이 남아있는 경우
                if nm//5:
                    # 모두 홀수이거나 짝수인 경우
                    if cnt == odd or cnt == even:
                        fireball.append([r, c, nm//5, ns//cnt, 0])
                        fireball.append([r, c, nm//5, ns//cnt, 2])
                        fireball.append([r, c, nm//5, ns//cnt, 4])
                        fireball.append([r, c, nm//5, ns//cnt, 6])
                    # 다른 방향이 있는 경우
                    else:
                        fireball.append([r, c, nm//5, ns//cnt, 1])
                        fireball.append([r, c, nm//5, ns//cnt, 3])
                        fireball.append([r, c, nm//5, ns//cnt, 5])
                        fireball.append([r, c, nm//5, ns//cnt, 7])

            # 배열의 위치에 파이어볼이 하나만 존재하는 경우 그대로 파이어볼 리스트에 다시 넣어준다.
            elif len(arr[r][c]) == 1:
                fireball.append([r, c] + arr[r][c].pop())


# 시행을 K번 반복한다.
for _ in range(K):
    move()
    merge_split()

# ans: 남아있는 파이어볼 질량의 합
ans = 0

# 남아있는 파이어볼 질량의 합을 더해준다.
for i in range(len(fireball)):
    ans += fireball[i][2]

# 정답 출력
print(ans)