242. 마법사 상어와 파이어볼

아현·2021년 8월 11일
0

Algorithm

목록 보기
253/400

백준




1. Python



import copy
from collections import deque

#0, 1, 2, 3, 4, 5, 6, 7
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

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

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

for _ in range(k):    
    new_board = [[deque() for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            while len(board[i][j]) > 0: 
                nx, ny = i, j
                m, s, d = board[i][j].popleft()
                #1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결
                nx = (nx + (s * dx[d])) % n
                ny = (ny + (s * dy[d])) % n
                new_board[nx][ny].append([m, s, d])
    board = copy.deepcopy(new_board)    

    for i in range(n):
        for j in range(n):
            isEven, isOdd = False, False 
            ms, ss = 0, 0 
            nm, ns = 0, 0 
            if len(board[i][j]) >= 2:                
                length = len(board[i][j])
                while board[i][j]:
                    m, s, d = board[i][j].popleft()
                    ms += m
                    ss += s
                    if d % 2 == 0:
                        isEven = True
                    else:
                        isOdd = True           
                nm = ms // 5  # 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
                ns = ss // length # 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
                if nm == 0:    # 질량이 0인 파이어볼은 소멸되어 없어진다.
                    continue
              
                if isEven == True and isOdd == True: # 방향이 홀수, 짝수가 섞여 있음 -> 방향이 1, 3, 5, 7
                    for nd in range(1, 8, 2):
                        board[i][j].append([nm, ns, nd])
                else:
                    for nd in range(0, 8, 2):
                        board[i][j].append([nm, ns, nd])           

answer = 0
for i in range(n):
    for j in range(n):
        if len(board[i][j]):
            for ball in board[i][j]:
                answer += ball[0]

print(answer)





속도 개선


from sys import stdin
dx = [-1,-1,0,1,1,1,0,-1]
dy = [0,1,1,1,0,-1,-1,-1]
n,m,k=map(int, stdin.readline().split())
balls=[]
for _ in range(m):
    r,c,m,s,d = map(int, stdin.readline().split())
    balls.append((r-1,c-1,m,s,d))
maps=[[[] for _ in range(n)] for _ in range(n)]

for _ in range(k):
    for i in range(len(balls)):
        r,c,m,s,d=balls[i]
        nr = (r+dx[d]*s)%n
        nc = (c+dy[d]*s)%n
        maps[nr][nc].append((nr,nc,m,s,d))

    balls.clear()
    
    for i in range(n):
        for j in range(n):
            if len(maps[i][j]) == 0 : 
            	continue
            elif len(maps[i][j]) == 1:
                balls.append(maps[i][j][0])
            else:
                sumM,sumS=0,0
                odd,even=0,0
                for r,c,m,s,d in maps[i][j]:
                    sumM+=m
                    sumS+=s
                    if d %2 == 0: 
                    	even+=1
                    else: 
                    	odd+=1
                sumM //= 5
                sumS //= len(maps[i][j])
                if sumM!=0:
                    if (not odd and even) or (not even and odd) :
                        for dir in range(0,8,2):
                            balls.append((i,j,sumM,sumS,dir))
                    else:
                        for dir in range(1,8,2):
                            balls.append((i,j,sumM,sumS,dir))
            maps[i][j].clear()
result=0

for r,c,m,s,d in balls:
    result+=m

print(result)

profile
For the sake of someone who studies computer science

0개의 댓글