[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)

 

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