[Python] 20057. 마법사 상어와 토네이도

www.acmicpc.net/problem/20057

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

 

---

Point

• 토네이도가 (0,0) 도달 시 종료
• 한칸 움직일 때마다 모래를 퍼트림

Tip

• 반시계 방향 회전가능할 때까지 전진
• 시간 절약을 위해 현 위치의 모래가 0이 아닐때만 (A[y][x] != 0) 모래를 퍼트림

메모리 (제한: 512MB)

132984 KB

시간 (제한: 1초)

476 ms

결과

100%

 

import sys
from collections import deque

def spread(y,x,one,seven,two,ten,five,alpha):
    global n, sand_out
    tmp = 0
    for d in one:
        ny = y + d[0]
        nx = x + d[1]
        sand = ground[y][x] // 100
        if 0 <= ny < n and 0 <= nx < n:
            ground[ny][nx] += sand
        else:
            sand_out += sand
        tmp += sand

    for d in seven:
        ny = y + d[0]
        nx = x + d[1]
        sand = ground[y][x] * 7 // 100
        if 0 <= ny < n and 0 <= nx < n:
            ground[ny][nx] += sand
        else:
            sand_out += sand
        tmp += sand

    for d in two:
        ny = y + d[0]
        nx = x + d[1]
        sand = ground[y][x] * 2 // 100
        if 0 <= ny < n and 0 <= nx < n:
            ground[ny][nx] += sand
        else:
            sand_out += sand
        tmp += sand

    for d in ten:
        ny = y + d[0]
        nx = x + d[1]
        sand = ground[y][x] * 10 // 100
        if 0 <= ny < n and 0 <= nx < n:
            ground[ny][nx] += sand
        else:
            sand_out += sand
        tmp += sand

    for d in five:
        ny = y + d[0]
        nx = x + d[1]
        sand = ground[y][x] * 5 // 100
        if 0 <= ny < n and 0 <= nx < n:
            ground[ny][nx] += sand
        else:
            sand_out += sand
        tmp += sand

    for d in alpha:
        ny = y + d[0]
        nx = x + d[1]
        sand = ground[y][x] - tmp
        if 0 <= ny < n and 0 <= nx < n:
            ground[ny][nx] += sand
        else:
            sand_out += sand
    ground[y][x] = 0

def sandstrom(y,x,i):
    if ground[y][x] != 0:
        if i == 0:
            spread(y, x, [(-1, 1), (1, 1)], [(-1, 0), (1, 0)], [(-2, 0), (2, 0)], [(-1, -1), (1, -1)], [(0, -2)], [(0, -1)])
        elif i == 1:
            spread(y, x, [(-1,-1),(-1,1)], [(0,-1),(0,1)], [(0,-2),(0,2)], [(1,-1),(1,1)], [(2,0)], [(1, 0)])
        elif i == 2:
            spread(y, x, [(-1, -1), (1, -1)], [(-1, 0), (1, 0)], [(-2, 0), (2, 0)], [(-1, 1), (1, 1)], [(0, 2)], [(0, 1)])
        else:
            spread(y, x, [(1, -1), (1, 1)], [(0, -1), (0, 1)], [(0, -2), (0, 2)], [(-1, -1), (-1, 1)], [(-2, 0)], [(-1, 0)])

def go(y,x):
    check = [[False] * n for _ in range(n)]
    i = 0
    ny, nx = y + dydx[i][0], x + dydx[i][1]
    check[y][x] = True
    check[ny][nx] = True
    queue = deque([[ny,nx,i]])
    sandstrom(ny,nx,i)
    while queue:
        y,x,i = queue.popleft()
        if (y,x) == (0,0):
            break
        ni = (i+1)%4
        ny,nx = y+dydx[ni][0],x+dydx[ni][1]
        if check[ny][nx]:
            ni = i
            ny,nx = y+dydx[ni][0],x+dydx[ni][1]
        check[ny][nx] = True
        queue.append([ny,nx,ni])
        sandstrom(ny, nx, ni)

input = sys.stdin.readline
n = int(input())
ground = [list(map(int, input().split())) for _ in range(n)]
dydx = ((0,-1),(1,0),(0,1),(-1,0))
sand_out = 0
go(n//2,n//2)
print(sand_out)

 

문제를 푸는데 도움이 된 테스트 케이스