[백준 20057] 마법사 상어와 토네이도

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

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

---

접근

다음 칸으로 이동했을 때 해당 칸의 모래의 양은 없어지고 미리 정해진 위치로 비율만큼 흩어지게 된다. 그리고 방향에 따라 특정 위치의 비율도 달라진다. 따라서 미리 방향에 따라 특정 위치로 이동했을 때의 비율을 저장해둔 후에 사용하도록 하였다.

 

아래와 같이 현재 위치와 방향을 기준으로 흩어지는 모래의 비율을 저장하였다. 행의 번호는 현재 방향을 가리키고 있는 인덱스가 되며 열은 해당 위치로 이동하기 위한 값, ratio는 특정 위치로 이동했을 때의 비율을 의미한다.

ty = [
    [-1, -1, -1, 1, 1, 1, -2, 2, 0],
    [-1, 0, 1, -1, 0, 1, 0, 0, 2],
    [-1, -1, -1, 1, 1, 1, -2, 2, 0],
    [-1, 0, 1, -1, 0, 1, 0, 0, -2],
]

tx = [
    [-1, 0, 1, -1, 0, 1, 0, 0, -2],
    [-1, -1, -1, 1, 1, 1, -2, 2, 0],
    [-1, 0, 1, -1, 0, 1, 0, 0, 2],
    [-1, -1, -1, 1, 1, 1, -2, 2, 0],

]

ratio = [
    [0.1, 0.07, 0.01, 0.1, 0.07, 0.01, 0.02, 0.02, 0.05],
    [0.01, 0.07, 0.1, 0.01, 0.07, 0.1, 0.02, 0.02, 0.05],
    [0.01, 0.07, 0.1, 0.01, 0.07, 0.1, 0.02, 0.02, 0.05],
    [0.1, 0.07, 0.01, 0.1, 0.07, 0.01, 0.02, 0.02, 0.05],
]

 

위와 같이 미리 정해두었다면 큰 어려움이 없었던 문제였다.

 

구현

• 토네이도로 이동할 때 좌 -> 하 -> 우 -> 상 순으로 이동하게 된다.
• 또한 좌 -> 하로 각각 1칸씩 이동 후에는 우 -> 상으로 각각 2칸씩 이동하는데 계속 진행하다보면 규칙을 찾을 수 있었다.
• 따라서 현재 방향으로 이동해야 하는만큼(total) 이동했다면(count == total) 방향을 증가시킨다.
• 방향을 증가시켰을 때 좌 또는 우일 때는 total을 증가시킨다.
• 다음 방향으로 이동 후에 모래가 있다면 토네이도를 통해 비율만큼 모래를 나눈다.

answer = 0
number = 0
cy, cx, cd = N//2, N//2, 0
count, total = 0, 1

while number < N ** 2:
    if count == total:
        count = 0
        cd = (cd + 1) % 4
        if cd == 0 or cd == 2:
            total += 1

    cy += dy[cd]
    cx += dx[cd]
    number += 1
    count += 1
    if board[cy][cx] > 0:
        board = tornado(cy, cx, cd, board)

• 현재 이동한 위치의 모래의 양을 m에 저장한다.
• 이제 현재 방향을 기준으로 모래를 비율만큼 나눈다.
• 만약 해당 위치가 범위를 벗어나면 answer에 저장하고 그렇지 않을 때는 해당 위치로 모래를 더한다.
• 이때 나눠진 모래들을 total에 더한다.
• 이제 마지막으로 현재 위치에서 현재 방향으로 한 칸 더 이동하여 원래의 전체 모래에서 나눠지지 않은 모래를 더한다.

def tornado(y, x, d, board):
    global answer
    m = board[y][x]
    board[y][x] = 0
    total = 0
    for i in range(9):
        ny = y + ty[d][i]
        nx = x + tx[d][i]
        r = ratio[d][i]
        if check_range(ny, nx):
            board[ny][nx] += int((m * r))
            total += int((m * r))
        else:
            answer += int((m * r))
            total += int((m * r))

    ny = y + dy[d]
    nx = x + dx[d]
    if check_range(ny, nx):
        board[ny][nx] += (m - total) if m - total > 0 else 0
    else:
        answer += (m - total) if m - total > 0 else 0

    return board

---

전체 코드

import sys
input = sys.stdin.readline

ty = [
    [-1, -1, -1, 1, 1, 1, -2, 2, 0],
    [-1, 0, 1, -1, 0, 1, 0, 0, 2],
    [-1, -1, -1, 1, 1, 1, -2, 2, 0],
    [-1, 0, 1, -1, 0, 1, 0, 0, -2],
]

tx = [
    [-1, 0, 1, -1, 0, 1, 0, 0, -2],
    [-1, -1, -1, 1, 1, 1, -2, 2, 0],
    [-1, 0, 1, -1, 0, 1, 0, 0, 2],
    [-1, -1, -1, 1, 1, 1, -2, 2, 0],

]

ratio = [
    [0.1, 0.07, 0.01, 0.1, 0.07, 0.01, 0.02, 0.02, 0.05],
    [0.01, 0.07, 0.1, 0.01, 0.07, 0.1, 0.02, 0.02, 0.05],
    [0.01, 0.07, 0.1, 0.01, 0.07, 0.1, 0.02, 0.02, 0.05],
    [0.1, 0.07, 0.01, 0.1, 0.07, 0.01, 0.02, 0.02, 0.05],
]

def check_range(y, x):
    return (0 <= y < N) and (0 <= x < N)

def tornado(y, x, d, board):
    global answer
    m = board[y][x]
    board[y][x] = 0
    total = 0
    for i in range(9):
        ny = y + ty[d][i]
        nx = x + tx[d][i]
        r = ratio[d][i]
        if check_range(ny, nx):
            board[ny][nx] += int((m * r))
            total += int((m * r))
        else:
            answer += int((m * r))
            total += int((m * r))

    ny = y + dy[d]
    nx = x + dx[d]
    if check_range(ny, nx):
        board[ny][nx] += (m - total) if m - total > 0 else 0
    else:
        answer += (m - total) if m - total > 0 else 0

    return board

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]

dy = [0, 1, 0, -1]
dx = [-1, 0, 1, 0]

answer = 0
number = 0
cy, cx, cd = N//2, N//2, 0
count, total = 0, 1

while number < N ** 2:
    if count == total:
        count = 0
        cd = (cd + 1) % 4
        if cd == 0 or cd == 2:
            total += 1

    cy += dy[cd]
    cx += dx[cd]

    number += 1
    count += 1
    if board[cy][cx] > 0:
        board = tornado(cy, cx, cd, board)

print(answer)