[백준] 20057번 / 마법사 상어와 토네이도 / 파이썬(Python)

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

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

풀이

마법사 상어가 또 뭐 배워서 나타났다.

먼저 토네이도가 부는 방향에 따라 움직이는 칸의 개수가 달라지는 점을 발견했다.

바람은 [왼, 아], [오, 위]가 짝지어 칸 이동 개수가 같으며 N*2번 분다. 바람이 N번 분다고 생각 하고, 한번 바람이 불때 방향 전환을 한번씩 한다. 무슨 말이냐.. 

for i in range(n):
    if i % 2 == 0:
        wind(i+1, 0, -1, 'left') # left
        wind(i+1, 1, 0, 'down') # down
    else:
        wind(i+1, 0, 1, 'right') # right
        wind(i+1, -1, 0, 'up') # up

홀/짝에 따라 바람 두번 불고, 방향전환은 1번 해준다. 그림과 홀짝이 다른 이유는 0부터 시작하기 때문.

 

이제 모래가 어떻게 흩날리는 것에 대해 생각해야한다. 모래는 미리 설정한 비율에 따라 흩날리게 되는데 문제는 방향이 달라질때마다 일정비율도 함께 회전 해야한다는 것이다. 이건 주사위굴리기(https://harami.tistory.com/36)와 유사하게 처리 할 수 있겠다. 주사위 굴리기는 각 숫자면이 움직이면서 이동하는 위치를 각자 저장해놓고 이용했다. 이것도 마찬가지로 4방향에 따라 모래가 흩날리는 비율을 다르게 저장해준다. 회전하기 때문에 한 방향에 저장된 행렬을 방향에 따라 회전했다. 조금만 생각해보면 어렵지 않게 위치를 바꿔 회전 할 수 있다.

 

코드만 보면 또 아주 쉬운 문젠가 싶지만 여러가지 생각해야할 점이 많아 어려운 문제였다.

 

코드

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

# 정답 누적 모래
result = 0
# 좌표 가운데 시작점
now = [n//2, n//2]

left = [[-2, 0, 0.02], [2, 0, 0.02], [-1, -1, 0.1], \
        [-1, 0, 0.07], [-1, 1, 0.01], [0, -2, 0.05], \
        [1, 0, 0.07], [1, -1, 0.1], [1, 1, 0.01], [0, -1, 0]]
right = [[x, -y, z] for x, y, z in left]
up = [[y, x, z] for x, y, z in left]
down = [[-y, x, z] for x, y, z in left]

rate = {'left' : left, 'right': right, 'up':up, 'down':down}

def wind(move, dx, dy, direct):
    global result
    for _ in range(move):
        now[0] = now[0] + dx
        now[1] = now[1] + dy
        # 퍼지는 모래 양 누적(알파 값 계산)
        spread = 0
        # 회오리가 끝난 경우
        if now[0] < 0 or now[1] < 0:
            break
        for rx, ry, r, in rate[direct]:
            nx = now[0] + rx
            ny = now[1] + ry
            # 퍼지지 않고 남은 모래
            if r == 0:
                sand = sand_map[now[0]][now[1]] - spread
            # 비율에 따라 퍼지는 모래양
            else:
                sand = int(sand_map[now[0]][now[1]] * r)
            # 회전 후, 범위 안에 존재한다면 모래양 누적
            if 0 <= nx < n and 0<= ny < n:
                sand_map[nx][ny] += sand
            # 회전 후, 범위 밖으로 퍼진 모래양 누적
            else:
                result += sand
            # 퍼지지 않은 모래 양 계산을 위해 퍼진 모래 누적
            spread += sand

for i in range(n):
    if i % 2 == 0:
        wind(i+1, 0, -1, 'left') # left
        wind(i+1, 1, 0, 'down') # down
    else:
        wind(i+1, 0, 1, 'right') # right
        wind(i+1, -1, 0, 'up') # up
print(result)