[BOJ][🟡4][백준#20056] 마법사 상어와 파이어볼

문제 출처

BAEKJOON Online Judge #20056

문제

어른 상어가 마법사가 되었고, 파이어볼을 배웠다. 마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다. 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.

7 0 1

6   2

5 4 3

마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.

모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.

이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.

이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.

같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다. 파이어볼은 4개의 파이어볼로 나누어진다. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.

질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.

질량이 0인 파이어볼은 소멸되어 없어진다.

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.

입력

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.

출력

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.

제한

4 ≤ N ≤ 50 0 ≤ M ≤ N2 1 ≤ K ≤ 1,000 1 ≤ ri, ci ≤ N 1 ≤ mi ≤ 1,000 1 ≤ si ≤ 1,000 0 ≤ di ≤ 7

예제

예제 1

입력

4 2 1
1 1 5 2 2
1 4 7 1 6

출력

8

예제 2

입력

4 2 2
1 1 5 2 2
1 4 7 1 6

출력

8

예제 3

입력

4 2 3
1 1 5 2 2
1 4 7 1 6

출력

0

예제 4

입력

7 5 3
1 3 5 2 4
2 3 5 2 6
5 2 9 1 7
6 2 1 3 5
4 4 2 4 2

출력

9

My Sol

def replace(k):
    global N
    if k < 0:
        while k < 0:
            k += N
    if k >= N:
        while k >= N:
            k -= N
    return k

def move():
    global N, mat, tog, t, direction
    for i in range(N):
        for j in range(N):
            while mat[i][j][t]:
                m, d, s = mat[i][j][t].pop()
                di, dj = direction[d]
                si, sj = replace(i+di*s), replace(j+dj*s)
                if not (0<=si<N and 0<=sj<N): continue
                mat[si][sj][tog[t]].append([m, d, s])
    t^=1


def union_and_divide():
    global N, mat, t, direction
    multi_fireball = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            dir = 1
            fireball_cnt = len(mat[i][j][t])
            if fireball_cnt > 1:
                multi_fireball[i][j] = 1
            while mat[i][j][t]:
                m, d, s = mat[i][j][t].pop()
                if not mat[i][j][t]: break
                std_dir = mat[i][j][t][0][1]
                if std_dir%2 != d%2: dir = 0
                mat[i][j][t][0][0] += m
                mat[i][j][t][0][2] += s

            if not fireball_cnt: continue
            if multi_fireball[i][j]:
                new_m = m//5
                if new_m:
                    new_s = s//fireball_cnt
                    for k in range(1-dir, 8, 2):
                        mat[i][j][tog[t]].append([new_m, k, new_s])
            else:
                mat[i][j][tog[t]].append([m, d, s])
    t^=1

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)
}

t = 0
tog = {1:0, 0:1}
N, M, K = map(int, input().split())
mat = [[[[], []] for _ in range(N)] for _ in range(N)]
for _ in range(M):
    r, c, mass, speed, direc = map(int, input().split())
    mat[r-1][c-1][t].append([mass, direc, speed])

for _ in range(K):
    move()
    union_and_divide()

# 카운트
ret = 0
for i in range(N):
    for j in range(N):
        while mat[i][j][0]:
            m, d, s = mat[i][j][0].pop()
            ret += m

print(ret)

다차원을 활용해야 하는 구현 문제였다. 절차대로 하면 어렵지 않으나, 문제에서 가볍게 설명하고 지나는 부분이 결정적인 요인이 많아 자세히 잘 읽어보아야 풀 수 있었다.

1. 입력을 받아 처리하는데, 2차원 배열 mat에 toggle 인자 t에 따른 0, 1의 오고감을 위하여 빈 배열 2개가 있는 1차원 배열을 mat의 각 영역마다 채워넣어 초기화한다. 즉, 3차원 배열이다.
2. K번 같은 패턴을 반복하므로 걱정없이 K만큼 for문을 돌리는데, 파이어볼이 움직이는 move 함수과 움직인 파이어볼들이 합쳐지고, 2개 이상이라면 나누어지는 union_and_divide 함수를 작성한다.
3. 파이어볼들의 방향에 따라 di, dj를 결정할 수 있도록 direction dictionary를 미리 두고, move 함수에서는 파이어볼들마다 direction dictionary에서 방향 벡터를, 그리고 속도를 여기에 곱해 현재 위치에 더하여 최종 이동 위치를 결정한다.
4. 여기서 중요한 점이 2가지 있는데, 첫째는 범위를 벗어난 파이어볼은 다시 구역 안으로 들어와야 하므로, 크기에 따라 N을 더하거나 빼주는 replace 함수를 만들어 이동 위치를 조정해주었다. 둘째는 기존 조회하는 fireball들의 t가 0에서 확인하는데, 새롭게 이동하는 fireball은 3차원 축이 1인 지점에 두어야 한다. 그래야 이후의 move를 위한 for문에서 이미 이동한 fireball이 조회를 피할 수 있다. 이것이 mat을 3차원 배열로 만든 이유이다.
5. 이후 3차원 축이 1인 지점을 조회하며 이동된 파이어볼들을 조회하는데, 각 위치에서 파이어볼이 2개 이상이라면 방향과 무게, 속도를 누적 및 확인하여 하나로 모아준다.
6. 만약 기존에 파이어볼이 없었다면 그냥 넘어가고, 1개만 있었다면 3차원 축이 0인 지점으로 파이어볼을 보내주며, 2개 이상이었다면 3차원 축이 0인 지점으로 현재 합쳐진 파이어볼을 4조각으로 쪼개 모두 넣어준다.
7. 이때 중요한 점은 지금 보내는 것이 아니라, 현재 위치에 4개의 파이어볼이 남아있는 것이며, 다음 move에서 각각의 파이어볼이 사방으로 퍼져나가는 것이다. 이것을 현재 턴에 해주지 않아야 문제를 해결할 수 있었다.
8. 모든 K를 마친다면 mat의 전체 픽셀을 완전탐색하며 3차원 축이 0인 배열의 fireball들 각 0번 인덱스 값을 모두 더하여 출력하면 된다.

정확히는 mat에 fireball(1차원)의 집합(2차원)이 2가지 경우가 있는(3차원) 것들이 NxN만큼(2차원) 있으므로 5차원의 계산이 필요하지만, 사실 크기가 그리 크지 않고 차원에 대한 계산이 많지 않아 이런 부분에서는 큰 어려움이 없다.

하지만 fireball이 나누어질 때 현재 턴에서는 현재 위치에 남아있다는 것이 오답을 피하는 데에 중요한 키포인트가 되겠다.

결과

맞았습니다!!

모범답안

출처

# empty