문제 링크
문제 설명
격자로 나누어진 N*N크기의 모래밭에서 토네이도를 연습한다. A[r][c]는 (r,c) 위치에 있는 모래의 양을 의미한다.
토네이도를 시전하면 다음과 같이 가운데칸부터 토네이도가 이동한다. 한번에 한칸씩만!
그리고 이동시에는 다음과 같은 비율로 흩날린다.
이는 왼쪽으로 이동시의 경우고, 다른 방향이면 그림을 해당 방향으로 회전한다. x에 있던 토네이도가 y로 이동시, y에 있던 모든 모래가 위와 같은 비율로 이동하고, 이동하고 남은 양이 a에 저장된다.
토네이도가 (1,1)까지 이동하고 소멸될때, 격자 밖으로 나간 모래의 양을 구하라
문제 풀이
토네이도 이동에 대한 구현
토네이도는 위의 그림과 같이 N=7인 경우, (3,3)->(3,2)->(4,2)->(4,3)->(4,4)->...->(0,0)까지 이동한다. 왼쪽 한칸 -> 아래쪽 한칸 -> 오른쪽 두칸 -> 위쪽 두칸 -> 왼쪽 세칸 -> 아래쪽 세칸 -> ... 등의 패턴을 가짐을 알 수 있다. 방향은 좌-하-우-상, 이동 칸수는 1칸부터 방향을 2번 바꾼 시점에 칸수가 1칸씩 늘어난다. 따라서 토네이도의 시작 좌표를 (x,y)라 했을때 다음과 같이 구현했다.
x, y, d = N//2, N//2, 0
count = 0 # moves만큼 두 방향동안 이동했는지?
cur_moves = 0 # 현재 이 방향으로 몇번 이동했는지?
moves = 1 # 이 방향으로 몇칸 이동해야 하는지?
while True:
# 이동 칸수/방향 갱신
if cur_moves == moves:
cur_moves = 0
count += 1
d = (d+1)%4
if count == 2:
count = 0
moves += 1
# 중심 1칸 이동하기
x, y = x+dx[d], y+dy[d]
# 모래 이동하기
move(x, y, d)
if (x,y) == (0,0):
# (0,0)까지 이동 완료했으면
break
cur_moves += 1모래 이동에 대한 구현
은 쉽지 않았다. .. . .
와 모래가 어떤 칸으로 흩날릴지 계산하는 부분이 까다로웠다.
일단 그림과 같이 "왼쪽"으로 토네이도가 이동하는 경우, 모래가 흩날릴 칸과 그 비율은 다음과 같다.
dis = [(0,-2), (-1,-1), (-1,0), (-1,1), (-2,0), (1,-1), (1,0), (1,1), (2,0)]
move_sand = [0.05, 0.1, 0.07, 0.01, 0.02, 0.1, 0.07, 0.01, 0.02]이를 현재 방향에 맞게 매번 갱신할 수 있는 방법이 뭘까 고민하다가, 방향(좌->하->우->상)에 맞게 0, 270, 180, 90도씩 좌표를 회전시키기로 했다.
원점 기준 좌표를 특정 각도만큼 회전하는 공식은 다음과 같다.
rad = degree * (math.pi / 180.0)
nx = round(math.cos(rad)*x - math.sin(rad)*y)
ny = round(math.sin(rad)*x + math.cos(rad)*y)이를 적용해서 이번 방향에 대한 이동 좌표를 계산하면 되는데, 나는 좌표를 (y,x)가 아닌 (x,y)로 접근해서,,, 한참 했갈렸다 ^_ㅠ,,,,
코드는 다음과 같다.
def move(x, y, d):
sand = A[x][y] # 움직일 모래의 총 량 (그림상 y위치의 모래양)
degree = [0, 270, 180, 90]
dis = [(0,-2), (-1,-1), (-1,0), (-1,1), (-2,0), (1,-1), (1,0), (1,1), (2,0)] # "좌" 기준 모래 이동 좌표
move_sand = [0.05, 0.1, 0.07, 0.01, 0.02, 0.1, 0.07, 0.01, 0.02] # 좌표마다의 이동 비율
this_dis = []
# 이번 방향에 대한 이동 좌표 구하기
for di in dis:
rad = degree[d] * (math.pi / 180.0)
ny = round(math.cos(rad)*di[1] - math.sin(rad)*di[0])
nx = round(math.sin(rad)*di[1] + math.cos(rad)*di[0])
this_dis.append((nx,ny))
moved = 0 # y에서 움직인 모래의 총량
global answer # 밖으로 빠진 모래의 양
#9칸에 대해서 이동
for i in range(9):
nx, ny = x+this_dis[i][0], y+this_dis[i][1]
moving_sand = int(sand*move_sand[i]) # 현재 칸으로 움직일 모래의 양
moved += moving_sand
if in_bound(nx, ny):
A[nx][ny] += moving_sand
else:
# 격자 밖으로 나간 모래 count
answer += int(sand*move_sand[i])
# a칸에 대해서 이동
ax, ay = x+dx[d], y+dy[d]
left = sand - moved
if in_bound(ax, ay):
A[ax][ay] += left
else:
answer += left
# y칸의 모래 0으로
A[x][y] = 0전체 코드
import sys
import math
input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
# 입력받기
N = int(input())
A = []
for _ in range(N):
A.append(list(map(int, input().split())))
answer = 0 # 격자 밖으로 나간 모래 양
# 범위내인지 판단
def in_bound(x, y):
if x in range(N) and y in range(N):
return True
return False
# 이동시키기
def move(x, y, d):
sand = A[x][y]
degree = [0, 270, 180, 90]
dis = [(0,-2), (-1,-1), (-1,0), (-1,1), (-2,0), (1,-1), (1,0), (1,1), (2,0)]
this_dis = []
# 이번 방향에 대한 이동 좌표 구하기
for di in dis:
rad = degree[d] * (math.pi / 180.0)
ny = round(math.cos(rad)*di[1] - math.sin(rad)*di[0])
nx = round(math.sin(rad)*di[1] + math.cos(rad)*di[0])
this_dis.append((nx,ny))
move_sand = [0.05, 0.1, 0.07, 0.01, 0.02, 0.1, 0.07, 0.01, 0.02]
moved = 0
global answer
#9칸에 대해서 이동
for i in range(9):
nx, ny = x+this_dis[i][0], y+this_dis[i][1]
moving_sand = int(sand*move_sand[i]) # 현재 움직일 모래의 양
moved += moving_sand
if in_bound(nx, ny):
A[nx][ny] += moving_sand
else:
# 격자 밖으로 나간 모래 count
answer += int(sand*move_sand[i])
# a칸에 대해서 이동
ax, ay = x+dx[d], y+dy[d]
left = sand - moved
if in_bound(ax, ay):
A[ax][ay] += left
else:
answer += left
# x,y 칸의 모래 계산
A[x][y] = 0
x, y, d = N//2, N//2, 0
count = 0 # moves만큼 2번 이동했는지?
cur_moves = 0 # 현재 이 방향으로 몇번 이동했는지?
moves = 1 # 이 방향으로 몇칸 이동해야 하는지?
while True:
if cur_moves == moves:
cur_moves = 0
count += 1
d = (d+1)%4
if count == 2:
count = 0
moves += 1
# 중심 1칸 이동하기
x, y = x+dx[d], y+dy[d]
# 모래 이동하기
move(x, y, d)
if (x,y) == (0,0):
# (0,0)까지 이동 완료했으면
break
cur_moves += 1
print(answer)소요시간
3시간 ㅠ
sin, cos는 대학수학 이후로 처음 보는거 같네,, 좌표 이동을 고민하는데 시간이 너무 오래걸렸돠
