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

문제 출처 :

www.acmicpc.net/problem/20056

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

문제 풀이:

• 이번 삼성기출의 오전 2번 문제이다. 이번 삼성 공채의 오전 코테는 최근 몇년간 나왔던 기출중에 가장 쉬웠다고 시험 본 날부터 소문이 자자햇는데 실제로 풀어보니 최근 몇년보다 훨씬 쉽게 나온 것 같다. (상반기에 쉽지않았어서 그런가?)
• 아무튼 이문제 같은 경우는 문제를 구현하는거보다 문제를 이해하는게 더 어려웠던 것 같다.
• 이 문제에서 실수가 많았던 부분은 3가지 이다.
  1. 모든 파이어볼이 이동을 먼저 한다 , 그 후에 2개 이상의 파이어볼칸에 대해 합병이 이뤄진다.
     -> 나의 경우 동시에 진행되는 것으로 잘못 이해하고 풀어서 어려운 문제라고 생각햇는데 아니였다..
  2. 합쳐지는 파이어볼의 방향에 대해서 합을 보는것이 아니라, 합쳐지는 방향이 모두 짝수 혹은 홀수여야 하는 거였다.
     ex) 합쳐지는 방향 2 2 2 2  -> 나눠지는 방향 0,2,4,6
           합쳐지는 방향 2 3 2 3  -> 나눠지는 방향 1,3,5,7
  3. 마지막으로 한번에 파이어볼이 이동하는 칸의 크기는 속력*방향이다. 이때 칸은 모두 연결 되어있어서 그부분을 처리해주는게 가장 까다롭지 않았나 생각한다.
     풀다본니 %(mod)을 이용하면 된다는 것은 바로 감이 왔지만 구체적으로 어떻게 진행해야하는지를 헷갈렸다.
     때문에 나는 maps을 넘어가는경우에 대해서 각각의 경우를 나눠서 직접 하드코딩을 진행하였다..(다른분들은 더 똑똑하게 푸셧을듯?)

from copy import deepcopy

n,m,k = map(int,input().split())
maps = [[[] for _ in range(n)] for _ in range(n)]

fire_location =set()

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())
    r-=1
    c-=1
    fire_location.add((r,c))
    maps[r][c].append((M,s,d))


def show():
    for i in range(n):
        print(maps[i])

for _ in range(k):
    #이동명령
    next_candidate =set()
    copy_maps = [[[] for _ in range(n)] for _ in range(n)]
    #show()
    while(fire_location):
        #모든 Fire 이동
        cur_x,cur_y = fire_location.pop()
        while(maps[cur_x][cur_y]):
            cur_m,cur_s,cur_d=maps[cur_x][cur_y].pop()
            if (cur_s * dx[cur_d] > 0):
                nx = cur_x + (cur_s * dx[cur_d]) % n
                if (nx >= n):
                    nx = nx - n
            else:
                nx = cur_x - abs(cur_s * dx[cur_d]) % n
                if (nx < 0):
                    nx = n - abs(nx)
            if (cur_s * dy[cur_d] > 0):
                ny = cur_y + (cur_s * dy[cur_d]) % n
                if (ny >= n):
                    ny = ny - n
            else:
                ny = cur_y - abs(cur_s * dy[cur_d]) % n
                if (ny < 0):
                    ny = n - abs(ny)
            copy_maps[nx][ny].append((cur_m, cur_s, cur_d))
            next_candidate.add((nx, ny))
    #print()
    #이동이 끝난 후 같은 위치에 2개 있는지 체크
    for i in range(n):
        for j in range(n):
            if(len(copy_maps[i][j])>1):
                total_m = 0
                total_s =0
                even_d = 0
                odd_d = 0
                cnt=0
                while(copy_maps[i][j]):
                    cur_m,cur_s,cur_d = copy_maps[i][j].pop()
                    total_m+= cur_m
                    total_s+= cur_s
                    if(cur_d%2==0):
                        even_d+=1
                    else:
                        odd_d+=1
                    cnt+=1
                m_ = total_m//5
                if(m_==0):
                    continue
                s_ = total_s//cnt
                if(even_d == cnt or odd_d == cnt):
                    dir_ =[0,2,4,6]
                else:
                    dir_ = [1,3,5,7]
                for k in range(4):
                    copy_maps[i][j].append((m_,s_,dir_[k]))
    maps = deepcopy(copy_maps)
    fire_location = deepcopy(next_candidate)

ans=0
#show()
for i in range(n):
    for j in range(n):
        if(len(maps[i][j])==1):
            ans += maps[i][j][0][0]
        else:
            for k in range(len(maps[i][j])):
                ans += maps[i][j][k][0]

print(ans)