문제 바로가기
문제:
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다. 토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다. 토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다. 토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다. 토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.
입력:
첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.
출력:
격자의 밖으로 나간 모래의 양을 출력한다.
풀이 :
일단 토네이도가 돌때 모래를 흩뿌리는 비율을 2차원 그래프로 나타낸다.
그리고 90도씩 돌려주면 방향마다 설정이 가느하므로 함수로 만들어 둔다.
방향은 좌 하 우 위 이다.
근데 칸수를 보면 1 1 2 2 3 3 4 4 이런식으로 간다
그럼 홀수 일때는 좌 하 짝수 일때는 우 위 로 bfs를 보내주면 된다.
좌표 이동후 -> 흩날리는 모래 체크하고 -> 그 다음 좌표로 남은것을 옮겨준다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n = int(input())
res_x = n // 2
res_y = n // 2
graph = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
left = [[0, 0, 0.02, 0, 0],
[0, 0.1, 0.07, 0.01, 0],
[0.05, 0, 0, 0, 0],
[0, 0.1, 0.07, 0.01, 0],
[0, 0, 0.02, 0, 0]]
def rotate(pattern):
return list(reversed(list(zip(*pattern)))) # 시계 방향 90도 회전
down = rotate(left)
right = rotate(down)
up = rotate(right)
res = 0
def solution(block, dx, dy, direction):
global res, res_x, res_y
for _ in range(block):
res_x += dx
res_y += dy
if res_y < 0: # 맵 밖
return False
sand = graph[res_x][res_y] # 현재 모래
graph[res_x][res_y] = 0 # 현재 위치 모래 일단 없앰
spread_sand = 0 # 퍼진 모래 양 / 나중에 남은양 땜에
# 퍼뜨리기
for i in range(-2, 3):
for j in range(-2, 3):
if direction[i + 2][j + 2] > 0: # 퍼질 모래 비율이 존재하면 0 이 아님
# 그 좌표가 뭐지 ?
nx = res_x + i
ny = res_y + j
# 얼마나 퍼지는거지 ?
sand_amount = int(sand * direction[i + 2][j + 2])
# 맵 밖으로 안 나가나? -? 그럼 이동
if 0 <= nx < n and 0 <= ny < n:
graph[nx][ny] += sand_amount # 격자 내에 있으면 모래 추가
# 나간다고?
else:
res += sand_amount # 결과에 추가
# 기존 좌표에서 날라간 모래
spread_sand += sand_amount
# 안 퍼진 모래는 그대로 다음으로 넘어가야함
remaining_sand = sand - spread_sand
nx = res_x + dx
ny = res_y + dy
if 0 <= nx < n and 0 <= ny < n:
graph[nx][ny] += remaining_sand
else:
res += remaining_sand
for block in range(1, n + 1):
# 좌 하
if block % 2 == 1:
# 좌로 홀수칸
solution(block, 0, -1, left)
# 아래로 홀수칸
solution(block, 1, 0, down)
# 우 위
elif block % 2 == 0:
# 우로 짝수칸
solution(block, 0, 1, right)
# 위로 짝수칸
solution(block, -1, 0, up)
print(res)
댓글