[python] BOJ 백준 20057: 마법사상어와 토네이도

1. 문제  

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

2. 입력   

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

3. 출력   

격자의 밖으로 나간 모래의 양을 출력한다.

4. 해결방법   

이 문제는 구현, 시뮬레이션 문제이다. 회오리가 도는 방향은 규칙이있는데, 왼쪽1-아래쪽1-오른쪽2-위쪽2-왼쪽3-아래쪽3-오른쪽4-위쪽4 이런식으로 진행이된다. 왼쪽아래쪽에 대해서는 홀수번만큼 진행하고, 오른쪽위쪽에 대해서는 짝수번만큼 진행하게 된다. 따라서 for문을 돌면서 i가 홀수라면 왼쪽, 아래쪽으로 퍼지게끔 , 짝수라면 오른쪽, 위쪽으로 퍼지게끔 함수를 실행해주면된다. 몇퍼센트의 모래가 퍼질것인지에대해서는 미리 좌표와 퍼센트를 저장해놓아야하고, 각 방향에 따라 다르게 설정을 해주어야한다. 

1) move 함수: 현재좌표를 업데이트 해준다음, 해당 좌표에 대해서 퍼지는 모래양을 계산해주면된다. 미리 설정해놓은 비율로 계산을 하되, 범위가 벗어나면 정답값에 누적하여 더해주고, 범위안에 들어오면 해당 좌표의 모래값을 업데이트 해주면된다. 회오리를 돌다가 끝날수도 있으므로 현재 좌표의 x좌표나 y좌표가 0보다 작게되면 탐색을 종료한다. 퍼지는 모래들 이외에 현재자리에 퍼지지 않는 모래양을 계산하기 위해서는 퍼지는 모래의 누적값을 계산해주어야한다. 

5) 구현코드   

N = int(input()) 
desert = [list(map(int, input().split())) for _ in range(N)] #전체 모래양  
answer=0 #밖으로 나간 모래양 
now = [ N//2, N//2] #현재 x좌표, y좌표
#왼쪽방향으로 퍼질때 
left = [(-2, 0, 0.02), (2, 0, 0.02), (-1, -1, 0.1), (-1, 0, 0.07), (-1, 1, 0.01), (1, -1, 0.1), (1, 0, 0.07), (1, 1, 0.01), (0, -2, 0.05), (0, -1, 0)] 
right = [(x, -y, z) for x, y, z in left] #오른쪽방향으로 퍼질때 
down = [(-y, x, z) for x, y, z in left] #아래쪽 방향으로 퍼질때 
up = [(-x, y, z) for x, y, z in down]  #위쪽방향으로 퍼질때 
rate = {'left': left, 'right': right, 'down': down, 'up': up} 

#모래를 흩날리는 함수 
def move(cnt, dx, dy, direction): 
  global answer 
  for _ in range(cnt + 1): 
    #현재좌표 업데이트 
    now[0], now[1] = now[0]+ dx, now[1] + dy 
    #회오리를 돌다가 끝나버린경우 
    if now[0] < 0 or now[1] < 0: 
      break 

    spreads = 0 #모래가 퍼진값을 누적한 양  
    for dx, dy, r in rate[direction]: #퍼지는 모래 계산 
      nx,ny = now[0] + dx, now[1] + dy 
      if r == 0: #퍼지지 않는 모래들은 현재 자리에 누적해주기 
        sand = desert[now[0]][now[1]] - spreads 
      else: #퍼지는 모래들 계산 
        sand = int(desert[now[0]][now[1]] * r)

      #모래양 업데이트    
      if 0 <= nx < N and 0 <= ny < N:#범위안 
        desert[nx][ny] += sand 
      else: #범위밖: 정답 누적값 업데이트  
        answer += sand 
      spreads += sand  #현재자리 계산을 위한 퍼지는 모래의 누적값 



for i in range(N): 
  if i % 2 == 0: 
    move(i, 0, -1, 'left') #왼쪽 
    move(i, 1, 0, 'down')  #아래쪽 
  else: 
    move(i, 0, 1, 'right') #오른쪽 
    move(i, -1, 0, 'up')  #위쪽 

print(answer)

 

⭐️난이도:  골드 3 ⭐️

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

20057번: 마법사 상어와 토네이도