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

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

 

❗풀이방법

• 각 단계별 new_graph 생성
• nx, ny는 음수 발생을 방지하기 위해 +n 후에 %n
• 각 위치에 요소가 2개 이상 담겨있는 경우에 파이어볼을 4개로 분할
• graph를 new_graph로 업데이트

 

❗코드

import sys
input = sys.stdin.readline



n, m, k = map(int, input().split(" "))

graph = [[[] for _ in range(n)] for _ in range(n)]


dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]


for _ in range(m):
    r, c, m, s, d = map(int, input().split(" "))
    graph[r-1][c-1].append([m, d, s])


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

    # 이동 위치할 위치 찾기
    for i in range(n):
        for j in range(n):

            if graph[i][j]:
                while graph[i][j]:
                    temp = graph[i][j].pop(0)
                    m = temp[0]
                    d = temp[1]
                    s = temp[2]

                    nx = (i + dx[d] * s + n) % n
                    ny = (j + dy[d] * s + n) % n

                    new_graph[nx][ny].append([m, d, s])


    # 4개로 분할
    for i in range(n):
        for j in range(n):

            if len(new_graph[i][j]) > 1:
                cnt = len(new_graph[i][j]) # 총 파이어볼 개수

                # 전부 합친 거
                total_m = sum([x[0] for x in new_graph[i][j]])
                total_s = sum([x[2] for x in new_graph[i][j]])

                m = total_m // 5
                s = total_s // cnt

                if m == 0:
                    new_graph[i][j] = []
                    continue


                # 방항 정리하고 파이어볼 심기
                direct = [x[1] for x in new_graph[i][j]]
                odd = 0
                even = 0
                for d in direct:
                    if d % 2 == 1: odd += 1
                    else: even += 1


                if odd == cnt or even == cnt:
                    next_direct = [0, 2, 4, 6]
                else:
                    next_direct = [1, 3, 5, 7]

                new_graph[i][j] = []
                for d in next_direct:
                    new_graph[i][j].append([m, d, s])
                    
    graph = new_graph



result = 0

for i in range(n):
    for j in range(n):
        if graph[i][j]:
            cnt = sum([x[0] for x in graph[i][j]])
            result += cnt

print(result)