20056 - 마법사 상어와 파이어볼

 

---

 

문제

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

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

 

풀이

각 칸에 파이어볼을 정보를 담고있는 리스트를 요소로 가지는 2차원 배열을 선언한다.

[[ [m1, s1, d1], [m2, s2, d2] ..] ] , [ [m3, s3, d3] ] , .... ]

[[ [m4, s4, d4] ], ....

 

와 같은 형태로 칸에 접근해서 반복문을 돌림으로써 모든 파이어볼의 정보를 알 수 있는 구조로 말이다.

 

이후에 로직은 1. 파이어 볼 이동, 2. 파이어볼의 합침과 분할로 이루어지면 된다.

 

단 이때 나는 추가적인 배열을 두개 더 선언했다.

(파이어볼 이동의 결과를 저장하는 배열, 파이어볼의 합침과 분할의 결과를 저장하는 배열)

빈 배열에 결과값을 저장함으로 최대한 코드를 단순하게 작성했다.

 

 

1. 파이어 볼 이동
   • 2차원 배열을 돌면서 한개라도 파이어볼이 있다면 현재위치 + 방향 * 속도 만큼 이동해주면 된다.
   • 단 해당 문제는 배열의 범위를 벗어나면 반대쪽에서 나타난다.
   • 만약 n이 5인데 0 의 위치에서 5만큼 이동해야할 경우, 한바퀴를 빙 돌아 제자리에 오는것이다. 
   • 식으로 나타내면  '현재위치%n' 으로 표현할 수 있다. 양수같은 경우에는 모두 처리 가능하다.
   • 음수일때는 ' n - ((-현재위치)%n) ' 으로 계산하면 원하는 값을 얻을 수 있다.
     • 단, '-현재위치%n' 이 0이 나오게 된다면 n-0 = n 으로, 범위를 벗어나게 된다. (배열은 0 ~ 4 니까)
       따라서 이 때만 0으로 예외처리를 해주면 된다. (한바퀴 빙 도는거임)
2. 파이어볼 합침과 분할
   • 파이어볼이 2개이상 있는 칸을 선택한다.
     • 1개 있는 칸이면 결과배열에 그대로 옮겨주면 된다.
   • 파이어볼들을 순회하면서 질량, 속도, 짝수인지 홀수인지 정보들을 수집한다.
   • 계산한 질량이 0 보다 클 경우에만 로직을 실행한다.
   • 만약 짝수도 있고 홀수도 있다면 방향을 [1, 3, 5, 7] 가지는 파이어볼을 저장해주면 된다.
   • 그게 아니라면 [0, 2, 4, 8] 방향을 가지는 파이어볼을 저장해주면 된다.

 

코드

import copy
from sys import stdin

def minusProcess(v):
    v = n - ((-v) % n)
    if v == n: return 0
    return v
def solution():
    # 결과배열을 선언한다.
    global board
    res_board = [[[] for _ in range(1) for _ in range(n)] for _ in range(n)]
    ans_board = [[[] for _ in range(1) for _ in range(n)] for _ in range(n)]

    # 배열을 순회하면서 파이어볼을 이동해준다.
    for i in range(n):
        for j in range(n):
            if len(board[i][j]) > 0:
                for val in board[i][j]:
                    m, s, d = val

                    nx = i+dx[d]*s
                    ny = j+dy[d]*s

                    if 0 < nx : nx = minusProcess(nx)
                    if 0 < ny : ny = minusProcess(ny)
                    res_board[nx%n][ny%n].append([m, s, d])

    # 결과 배열에서 파이어볼이 2개이상 있는 칸의 처리를 시작한다.
    # 알아야 하는 값들 <총 질량, 총 속력, 개수, 모두 홀수인지 or 모두 짝수인지>
    for i in range(n):
        for j in range(n):
            if len(res_board[i][j]) >= 2:

                isOdd = False
                isEven = False
                totalM = 0
                totalS = 0
                totalNum = len(res_board[i][j])

                for val in res_board[i][j]:
                    m, s, d = val
                    totalM += m
                    totalS += s
                    if d%2 == 1:
                        isOdd = True
                    else:
                        isEven = True

                resM = totalM//5
                resS = totalS//totalNum

                evenDir = [0, 2, 4, 6]
                oddDir = [1, 3, 5, 7]

                # 합한 질량이 0보다 큰 경우
                if resM > 0:
                    for idx in range(4):
                        # 홀짝 섞여있는 경우
                        if isOdd and isEven:
                            ans_board[i][j].append([resM, resS, oddDir[idx]])
                        else:
                            ans_board[i][j].append([resM, resS, evenDir[idx]])
            else:
                ans_board[i][j] = res_board[i][j]
    board = copy.deepcopy(ans_board)


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 = [ [[] for _ in range(1) for _ in range(n)]  for _ in range(n) ]

for _ in range(m):
    r, c, m, s, d = map(int, stdin.readline().rstrip().split())
    # 질량, 속도, 방향
    board[r-1][c-1].append([m, s, d])

for _ in range(k):
    solution()

answer = 0
for i in range(n):
    for j in range(n):
        for val in board[i][j]:
            answer += val[0]
print(answer)

 

후기

 

급하게 푼다고 처음에 순회되는 배열인지 몰랐다 ㅋㅋ.. 이것만 깔끔하게 처리하면 큰 어려움은 없는 문제같다.