[BOJ][🟡3][백준#20057] 마법사 상어와 토네이도

문제 출처

BAEKJOON Online Judge #20057

문제

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 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] 이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다.

제한

3 ≤ N ≤ 499 N은 홀수 0 ≤ A[r][c] ≤ 1,000 가운데 칸에 있는 모래의 양은 0

예제

예제 1

입력

5
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0
0 0 0 0 0

출력

10

예제 2

입력

5
0 0 0 0 0
0 0 0 0 0
0 100 0 0 0
0 0 0 0 0
0 0 0 0 0

출력

85

예제 3

입력

7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 0 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7

출력

139

예제 4

입력

5
100 200 300 400 200
300 243 432 334 555
999 111 0 999 333
888 777 222 333 900
100 200 300 400 500

출력

7501

예제 5

입력

5
0 0 100 0 0
0 0 100 0 0
0 0 0 0 0
0 0 100 0 0
0 0 100 0 0

출력

283

예제 6

입력

9
193 483 223 482 858 274 847 283 748
484 273 585 868 271 444 584 293 858
828 384 382 818 347 858 293 999 727
818 384 727 373 636 141 234 589 991
913 564 555 827 0 999 123 123 123
321 321 321 983 982 981 983 980 990
908 105 270 173 147 148 850 992 113
943 923 982 981 223 131 222 913 562
752 572 719 590 551 179 141 137 731

출력

22961

My Sol

import sys
input = sys.stdin.readline

def move_line():
    global ci, cj, direction, try_cnt
    for _ in range((try_cnt + 2) // 2):
        di, dj = direction[try_cnt % 4]
        move_one(di, dj)
        ci += di
        cj += dj
    try_cnt += 1

def move_one(di, dj):
    global ci, cj, try_cnt, direction, mat
    if ci == cj == 0: return
    stdi, stdj = ci+di, cj+dj
    stdv = mat[stdi][stdj]
    mat[stdi][stdj] = 0
    p1 = int(stdv*0.01)
    p2 = int(stdv*0.02)
    p5 = int(stdv*0.05)
    p7 = int(stdv*0.07)
    p10 = int(stdv*0.10)
    last = stdv - 2*(p1+p2+p7+p10) - p5

    # 위아래 이동
    if try_cnt%2:
        check(stdi, stdj+1, p7)
        check(stdi, stdj-1, p7)
        check(stdi, stdj+2, p2)
        check(stdi, stdj-2, p2)
        check(stdi+di, stdj+1, p10)
        check(stdi+di, stdj-1, p10)
        check(stdi-di, stdj+1, p1)
        check(stdi-di, stdj-1, p1)
        check(stdi+di*2, stdj, p5)
        check(stdi + di, stdj, last)

    # 왼쪽 오른쪽 이동
    else:
        check(stdi+1, stdj, p7)
        check(stdi-1, stdj, p7)
        check(stdi+2, stdj, p2)
        check(stdi-2, stdj, p2)
        check(stdi+1, stdj+dj, p10)
        check(stdi-1, stdj+dj, p10)
        check(stdi+1, stdj-dj, p1)
        check(stdi-1, stdj-dj, p1)
        check(stdi, stdj+dj*2, p5)
        check(stdi, stdj + dj, last)

def check(i, j, v):
    global global_ans, mat, N
    if 0<=i<N and 0<=j<N:
        mat[i][j] += v
    else:
        global_ans += v

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

direction = {
    0: (0, -1),
    1: (1, 0),
    2: (0, 1),
    3: (-1, 0)
}
try_cnt = 0
ci = cj = N//2
global_ans = 0

move_line()
while not (ci==0 and cj==-1):
    for _ in range(4):
        move_line()

print(global_ans)

꽤나 번거롭기도 하고, 문제의 해석이 어렵기도 했던 문제였다. 모래들이 날아가면, 날아간 모래의 나머지가 알파라는 것인데, 제대로 알고 난 뒤에나 문제가 제시한 말이 무엇인지 알게되는 문제였다.

1. 2차원 배열의 입력을 처리한다.
2. 중앙부터 시작하기 때문에 기준점 ci, cj는 N//2로 둔다. NxN 2차원 배열의 중앙 인덱스이다.
3. move_line 함수는 방향과 상관 없이 실행하면 하나의 방향으로 계속 진행한다.
4. try_cnt 변수를 하나씩 올려가면서 move_line 함수의 길이와 방향을 결정한다.
5. 모든 회전이 왼쪽으로 가는 방향으로 끝이 나고, 시작도 왼쪽으로 가므로, 처음 move_line을 한 번 호출한 뒤, 4번을 호출하며 현재 위치가 끝에 도달했는지 확인한다.
6. move_line 함수는 한 칸씩 이동하며 모래를 옮겨가는 move_one 함수의 길이와 방향을 결정한다. 그리고 한 라인을 모두 이동하면 try_cnt를 늘리며 다음 회전을 위한 대비를 한다.
7. move_one 함수는 이동하는 위치의 모래와 비율을 계산해 주변의 좌표로 날려버린다. 격자 밖으로 나간 모래의 양은 global_ans 변수에 따로 누적해둔다.
8. 모든 회전이 끝나면 global_ans를 출력한다.

결과

맞았습니다!!