[파이썬/python] 백준 - 20057 마법사 상어와 토네이도

문제

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

---

문제 설명

1. 마법사 상어는 N*N 크기의 모래밭에서 토네이도 마법을 연습한다.
   1. 각 (r,c)의 값은 모래의 양을 의미한다.
   2. 격자의 중앙부터 토네이도가 시작된다.(예시는 그림으로 대체)
2. 토네이도 위치가 x일 때 y에 있는 모래가 각 비율, a위치로 뿌려지게 된다.
   1. a위치의 모래는 비율로 뿌린 모래의 나머지다.
3. 토네이도가 (0,0)으로 이동하게 되면, 소멸된다.
4. 토네이도가 소멸되었을 때, 격자 밖으로 나간 모래의 양을 구한다

토네이도 이동 예시

흩뿌리는 모래 위치

---

풀이

마법사 상어 기출 문제들 중 가장 쉽게 풀린 문제이다.

단순히 네 방향으로 이동할 때 흩뿌려지는 좌표를 하나하나 계산해서 모래를 넣어주기만 하면 된다.

1. 방향을 정의하고 왼쪽부터 토네이도를 시작한다.
2. 방향에 따라 모래를 흩뿌린다.
   1. 이 때 흩뿌리는 위치의 모래가 격자 밖으로 나가게 되면 결과 변수에 값을 계속해서 더해준다.
3. 최종적으로 (0,0)에 도달하게 되면 토네이도를 진행하는 while문을 탈출한다.
4. 격자 밖으로 나간 모래의 개수를 출력한다.

---

코드

import sys
input = sys.stdin.readline

N = int(input())

dir = {0: (0,-1), 1: (1,0), 2: (0,1), 3: (-1,0)}

board = [list(map(int,input().split())) for _ in range(N)]
d = 1
res = 0
def tornado(y,x,d):
    global res
    least = 0
    #왼쪽
    if d == 0:
        for ny,nx,rate in [(y-1,x,0.07), (y-2,x,0.02), (y+1,x,0.07), (y+2,x,0.02), (y+1,x+1,0.01), (y-1,x+1,0.01), (y+1,x-1,0.1), (y-1,x-1,0.1), (y,x-2,0.05)]:
            crnt_sand = int(board[y][x]*rate)
            least += crnt_sand
            if ny < 0 or ny > N-1 or nx < 0 or nx > N-1:
                res += crnt_sand
                continue
            board[ny][nx] += crnt_sand

        least_sand = board[y][x] - least
        if x-1 < 0 or x-1 > N-1:
            res += least_sand
        else:
            board[y][x-1] += least_sand
        board[y][x] = 0

    #아래쪽
    if d == 1:
        for ny,nx,rate in [(y,x-1,0.07), (y,x-2,0.02), (y,x+1,0.07), (y,x+2,0.02), (y-1,x+1,0.01), (y-1,x-1,0.01), (y+1,x+1,0.1), (y+1,x-1,0.1), (y+2,x,0.05)]:
            crnt_sand = int(board[y][x]*rate)
            least += crnt_sand
            if ny < 0 or ny > N-1 or nx < 0 or nx > N-1:
                res += crnt_sand
                continue
            board[ny][nx] += crnt_sand

        least_sand = board[y][x] - least
        if y+1 < 0 or y+1 > N-1:
            res += least_sand
        else:
            board[y+1][x] += least_sand
        board[y][x] = 0      

    #오른쪽
    if d == 2:
        for ny,nx,rate in [(y-1,x,0.07), (y-2,x,0.02), (y+1,x,0.07), (y+2,x,0.02), (y+1,x-1,0.01), (y-1,x-1,0.01), (y+1,x+1,0.1), (y-1,x+1,0.1), (y,x+2,0.05)]:
            crnt_sand = int(board[y][x]*rate)
            least += crnt_sand
            if ny < 0 or ny > N-1 or nx < 0 or nx > N-1:
                res += crnt_sand
                continue
            board[ny][nx] += crnt_sand

        least_sand = board[y][x] - least
        if x+1 < 0 or x+1 > N-1:
            res += least_sand
        else:
            board[y][x+1] += least_sand
        board[y][x] = 0

    #위쪽
    if d == 3:
        for ny,nx,rate in [(y,x-1,0.07), (y,x-2,0.02), (y,x+1,0.07), (y,x+2,0.02), (y+1,x+1,0.01), (y+1,x-1,0.01), (y-1,x+1,0.1), (y-1,x-1,0.1), (y-2,x,0.05)]:
            crnt_sand = int(board[y][x]*rate)
            least += crnt_sand
            if ny < 0 or ny > N-1 or nx < 0 or nx > N-1:
                res += crnt_sand
                continue
            board[ny][nx] += crnt_sand

        least_sand = board[y][x] - least
        if y-1 < 0 or y-1 > N-1:
            res += least_sand
        else:
            board[y-1][x] += least_sand
        board[y][x] = 0        

y,x = N//2,N//2
cnt = 1
d = -1
t = 0
while cnt < N:
    if cnt == N-1:
        t += 1
    for i in range(2+t):
        d = (d+1) % 4
        for j in range(cnt):
            y += dir[d][0]
            x += dir[d][1]
            tornado(y,x,d)
    cnt += 1
print(res)

---

시간복잡도

• 토네이도는 총 $N^2$회 만큼 진행되며, 최악의 경우 $N = 499$이다. 
• 각 토네이도를 진행할 때 총 10개의 위치를 탐색하게 된다.
• 계산하기 쉽게 $N = 500$이라고 가정하자. 결과적으로 $500*500*10 = 2500000 = 10^6$의 연산을 가진다.
• 따라서 약 $O(10^6)$의 시간복잡도가 소요된다.