[파이썬/python] 백준 - 20056 마법사 상어와 파이어볼

 

문제

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

---

문제 설명

1. 마법사 상어는 N*N 격자에 파이어볼 M개를 발사한다.
2. 각 파이어볼의 위치는 (r,c), 질량은 m, 방향은 d, 속력은 s 이다.
3.  1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
4. 마법사 상어가 파이어 볼에게 명령을 내린다. 
   1. 모든 파이어볼이 자신의 방향 d로 속력 s칸 만큼 이동한다.
      1. 이 때 같은 위치에 여러 개의 파이어볼이 이동할 수 있다.
   2. 이동이 끝난 후
      1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진 후 나뉘어진다.
         
         1. 질량은 ⌊ 합쳐진 파이어볼 질량의 합 / 5 ⌋ 이다.
         2. 속력은⌊ (합쳐진 파이어볼 속력의 합 / 합쳐진 파이어볼의 개수)⌋ 이다.
         3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 짝수이면, [0,2,4,6]이 되고, 그렇지 않으면 [1,3,5,7]이 된다.
         4. 질량이 0인 파이어볼은 소멸된다.
         5. ⌊ X ⌋ : X를 넘지 않는 정수를 의미한다. Ex) 1.5 -> 1
5. K번 명령한 후 남아있는 질량의 합을 구한다.

---

풀이

문제를 제대로 읽지 않아서 놓친 부분이 몇 개 있었다.

 

1. 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.

처음엔 파이어볼이 격자를 나가게 되면 생성하지 않았는데, 문제를 다시 읽어보니 격자의 맨 끝과 끝은 이어져 있었다. 왼쪽으로 넘어가면 다시 오른쪽으로 이동하면 된다.

 

2. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진 후 나누어진다.

처음엔 파이어볼이 나누어질 때 각 4방향으로 갈라져서 나누어지는 줄 알았다. 하지만 그게 아니었다.

파이어볼은 방향만 다르게 갈라지는 것이고 위치는 이동하지 않았다.

(r,c)에 존재하는 파이어볼이 4개로 갈라지면 (r,c,0), (r,c,2), (r,c,4), (r,c,6)으로 나뉘는 것이다. 이걸 몰라서 삽질을 많이 했다..

 

이 문제를 구현할 때 이동 후 모습을 deepcopy로 가져오다 보니, 시간이 많이 소요되었다. 배열만 가지고 이동하면 훨씬 더 빠르게 작동이 가능할 것 같다.

1. 초기 파이어볼의 위치를 fb 딕셔너리에 저장한다.
2. 각 위치를 탐색하며 파이어볼을 이동하여 next_fb 딕셔너리에 저장한다.
3. 이동 후 파이어볼들을 하나씩 검사하며, 나눠야 하는 파이어볼이 있는지 검사한다.
   1. 이 때 파이어볼들의 방향이 모두 짝수, 홀수인 경우 [0,2,4,6] 방향으로 4개의 파이어볼을 생성한다.
   2. 그렇지 않을 경우 [1,3,5,7] 방향으로 4개의 파이어볼을 생성한다.
4. 최종 divided_fb를 fb로 복사한다.
5. 2-4과정을 K번 반복 후 질량의 합을 출력한다.

---

코드

import sys
from copy import deepcopy
input = sys.stdin.readline

N,M,K = map(int,input().split())

dr = [-1,-1,0,1,1,1,0,-1]
dc = [0,1,1,1,0,-1,-1,-1]

fb = {}
for _ in range(M):
    r,c,m,s,d = map(int,input().split())
    #0: 질량, 1: 속력, 2:방향
    fb[(r-1,c-1)] = [[m,s,d]]

def convert_pos(y,x):
    if y < 0:
        ny = abs(y)
        if ny % N == 0:
            ny %= N
        else:
            ny = N-(ny%N)
    else:
        ny = abs(y)
        ny %= N
    if x < 0:
        nx = abs(x)
        if nx % N == 0:
            nx %= N
        else:
            nx = N-(nx%N)
    else:
        nx = abs(x)
        nx %= N
    return (ny,nx)

def create_fb(nfb,r,c,m,s,d):
    if (r,c) in nfb:
        nfb[(r,c)].append([m,s,d])
    else:
        nfb[(r,c)] = [[m,s,d]]

def move():
    global fb
    next_fb = {}
    #이동
    for r,c in deepcopy(list(fb.keys())):
        for i in range(len(fb[(r,c)])):
            m,s,d= fb[(r,c)][i][0], fb[(r,c)][i][1], fb[(r,c)][i][2]
            nr = r + dr[d]*s
            nc = c + dc[d]*s
            nr,nc = convert_pos(nr,nc)
            create_fb(next_fb,nr,nc,m,s,d)
    #검사
    divided_fb = {}
    for r,c in deepcopy(list(next_fb.keys())):
        total_fb = len(next_fb[(r,c)])
        if total_fb > 1:
            #파이어볼 나누기
            m = sum(next_fb[(r,c)][i][0] for i in range(total_fb)) // 5
            if m == 0:
                continue
            s = sum(next_fb[(r,c)][i][1] for i in range(total_fb)) // total_fb
            check = [0,0]
            for i in range(total_fb):
                if next_fb[(r,c)][i][2] % 2 == 0:
                    check[0] += 1
                else:
                    check[1] += 1
            if check[0] == 0 or check[1] == 0:
                for d in [0,2,4,6]:
                    create_fb(divided_fb,r,c,m,s,d)
            else:
                for d in [1,3,5,7]:
                    create_fb(divided_fb,r,c,m,s,d)
        else:
            create_fb(divided_fb,r,c,next_fb[(r,c)][0][0],next_fb[(r,c)][0][1],next_fb[(r,c)][0][2])
    fb = deepcopy(divided_fb)

for _ in range(K):
    move()

res = 0
for fireballs in fb.values():
    for fireball in fireballs:
        res += fireball[0]
print(res)

---

시간복잡도

• 시뮬레이션 문제다 보니, 시간이 넉넉할 거라고 생각하고 deepcopy를 생각 없이 사용했더니 아슬아슬하게 통과했다. 시뮬레이션 문제라도 시간복잡도를 꼼꼼하게 체크해야 할 것 같다.
•  한 번 명령 시 M개의 파이어볼을 이동한다. 명령은 총 K회 진행한다.
• $M = 1000, K = 1000$ 이므로 약 $O(K*M) = O(10^6)$의 시간복잡도가 소요된다.
  (실제로는 deepcopy 연산 및 파이어볼 나누기 연산 때문에 추가 상수만큼의 시간복잡도가 더해서 $O(10^7)$ 정도 될 것 같다.)