[python] BOJ 백준 20056: 마법사상어와 파이어볼

1. 문제  

어른 상어가 마법사가 되었고, 파이어볼을 배웠다. 마법사 상어가 크기가 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

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

1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
   • 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
   1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
   2. 파이어볼은 4개의 파이어볼로 나누어진다.
   3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
      1. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
      2. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
      3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
   4. 질량이 0인 파이어볼은 소멸되어 없어진다.

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

2. 입력   

첫째 줄에 N, M, K가 주어진다.

둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다.

서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.

3. 출력   

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

4. 해결방법   

이 문제는 구현, 시뮬레이션 문제이다. 파이어볼이 이동하는 명령에 대해서 순서대로 move함수를 구현해주고, K번 반복시켜준 후에 모든 파이어볼의 질량을 합해주면된다. 파이어볼의 행,열,질량,속력,방향에 대한 정보를 가지고 있는 배열을 만들어주고 move함수를 실행할때마다 업데이트해주었다. 

1) move 함수: 겹치는 파이어볼을 체크하기 위해서는 임시배열을 만들어주고, 한칸에 여러 파이어볼이 담기는지 파악해야한다. 파이어볼 배열을 돌면서 파이어볼을 한칸씩 속력이 다할때까지 움직여주면되는데, 경계를 넘어가면 다시 처음이나 끝으로 돌아가므로 각각 조건을 따로 달아주어 조정을 해주어야한다. (1번행은 n번과 연결되어있고 1번열은 n번열과 연결되어있다라고 했기 때문) 파이어볼을 모두 움직인 후 임시배열에 저장했다면, 임시배열을 돌면서 한칸에 2개 이상의 파이어볼이 담긴 곳을 찾아 합쳐주어야한다. 조건에 따라 질량, 속력, 방향을 합쳐주고 4개의 파이어볼로 생성을 해준다. 한칸에 하나만 담긴 파이어볼은 정상적으로 그대로 fire배열에 저장해주면된다. 

5) 구현코드   

N,M,K=map(int,input().split())
fire=[] #파이어볼 배열 
for _ in range(M):
  a,b,c,d,e=map(int,input().split())
  fire.append([a-1,b-1,c,d,e]) #행,열,질량,속력,방향 
#8가지 방향 
dx=[-1,-1,0,1,1,1,0,-1]
dy=[0,1,1,1,0,-1,-1,-1]


def move(fire):
  #임시배열 생성 (겹치는 파이어볼 체크)
  temp=[[[]for j in range(N)] for _ in range(N)]
  for i in range(len(fire)):
    if fire[i]:
      r,c,m,s,d=fire[i] #행,열,질량,속력,방향
      dis=s
      while dis: 
        r,c=r+dx[d],c+dy[d]
        #범위벗어나면 다시 연결  
        if r<0: r=N-1
        if r>=N: r=0
        if c<0 : c=N-1
        if c>=N: c=0
        dis-=1
      temp[r][c].append([i,m,s,d]) #임시배열에 저장 
  
  fire=[] #파이어볼 배열 초기화 
  for i in range(N):
    for j in range(N):
      weight,speed,direct=0,0,0 #누적질량, 누적속력, 누적방향 
      if len(temp[i][j])>1: #2개 이상의 파이어볼
        for num,m,s,d in temp[i][j]:
          weight+=m #누적질량 
          speed+=s #누적속력
          if d%2==0: direct+=1 #방향 짝수면 +1
        weight=weight//5 #최종 질량 
        speed=speed//len(temp[i][j]) #최종 속력 
        #방향 모두 짝수이거나 홀수인 경우 
        if direct==0 or direct==len(temp[i][j]): 
          merge=[0,2,4,6]
        else: #아닌경우 
          merge=[1,3,5,7]
    
        if weight!=0:#질량이 0아닐때만 
          for m in merge: #파이어볼 4개로 나눠짐 
            fire.append([i,j,weight,speed,m])
      #파이어볼 1개인 경우 
      elif len(temp[i][j])==1:
        num,m,s,d=temp[i][j][0]
        fire.append([i,j,m,s,d]) #그대로 추가 

  return fire
        
#K번반복 
for _ in range(K):
  fire=move(fire)

result=0 
for i in range(len(fire)):
  if fire[i]: #파이어볼 질량 합 
    result+=fire[i][2]
    
print(result)

 

⭐️난이도:  골드 4 ⭐️

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

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