[BOJ20057 - Python] 마법사 상어와 토네이도

문제

---

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

 

토네이도 이동 방향

 

토네이도가 x에서 y로 이동 시, y에 있던 모든 모래가 해당 비율만큼 이동한다. (소수점 아래는 버림)

비율이 적혀있는 칸으로 이동하지 않은 남은 모래는 전부 𝛼로 이동한다.

 

토네이도가 다른 방향으로 이동하는 경우, 위의 비율을 해당 방향으로 회전하면 된다.

토네이도가 (1, 1)까지 이동한 뒤 소멸되었을 때 격자 밖으로 나간 모래의 양을 구하는 것이 문제이다.

 

 

풀이

---

핵심으로 고려해야 했던 것은 토네이도 이동 방향에 따라 회전하는 모래의 흩날리는 비율과 𝛼에 대한 처리였다.

 

우선 모래가 흩날리는 비율을 5 × 5로 저장, 𝛼의 위치에는 -1을 저장하였다.

(𝛼는 맨 마지막에 처리해주어야 하기 때문에 격자 상에서의 𝛼 위치를 저장하기 위함)

# 모래 흩날리는 비율 (a 위치 : -1)
ratio = [[0, 0, 0.02, 0, 0], [0, 0.1, 0.07, 0.01, 0], [0.05, -1, 0, 0, 0], [0, 0.1, 0.07, 0.01, 0],
         [0, 0, 0.02, 0, 0]]

 

토네이도의 이동 방향을 보니, ←, ↓, →, ↑ 를 계속 반복하고 있었다.

 

이에 따라 방향이 바뀔 때마다,

ratio 배열 자체가 반 시계 방향으로 90도씩 회전한 것으로 변경되도록 함수를 만들어주면 어떨까 생각하게 되었다.

 

* old = ratio로 선언하면 얕은 복사가 일어나게 되므로, copy.deepcopy(ratio)로 깊은 복사를 해주었다.

# ratio 반 시계 방향 90도 회전
def rotate_ratio():
    old = copy.deepcopy(ratio)
    for i in range(1, 4):  # 대각선
        ratio[i][i] = old[i][-i - 1]
        ratio[i][-i - 1] = old[-i - 1][-i - 1]
    for i in range(5):  # 십자
        ratio[i][2] = old[2][-i - 1]
        ratio[2][i] = old[i][2]

 

따라서 토네이도가 이동했을 때마다 ratio 배열에 있는 값을 통해 해당 격자로 흩날릴 모래의 양을 계산하여 더해주고,

마지막에 𝛼의 위치에 비율이 적혀있는 칸으로 이동하지 않은 남은 모래를 더해주면 되는 것이다.

 

 

전체 코드는 다음과 같다.

import copy
import sys

N = int(sys.stdin.readline().strip())

grid = []  # N x N 격자
for _ in range(N):
    grid.append(list(map(int, sys.stdin.readline().split())))

# 0 : ← / 1 : ↓ / 2 : → / 3 : ↑
d_y = [0, 1, 0, -1]
d_x = [-1, 0, 1, 0]

# 모래 흩날리는 비율 (a 위치 : -1)
ratio = [[0, 0, 0.02, 0, 0], [0, 0.1, 0.07, 0.01, 0], [0.05, -1, 0, 0, 0], [0, 0.1, 0.07, 0.01, 0],
         [0, 0, 0.02, 0, 0]]


# ratio 반 시계 방향 90도 회전
def rotate_ratio():
    old = copy.deepcopy(ratio)
    for i in range(1, 4):  # 대각선
        ratio[i][i] = old[i][-i - 1]
        ratio[i][-i - 1] = old[-i - 1][-i - 1]
    for i in range(5):  # 십자
        ratio[i][2] = old[2][-i - 1]
        ratio[2][i] = old[i][2]


d = []  # 토네이도 이동 방향
i = 1
d_idx = 0
for _ in range(N - 1):
    for _ in range(2):
        for _ in range(i):
            d.append(d_idx)
        d_idx = (d_idx + 1) % 4
    i += 1
for _ in range(i):
    d.append(d_idx)

y, x = N // 2, N // 2  # 시작점 (y, x)
a_y, a_x = 0, 0  # a 위치 (a_y, a_x)
d_idx = d[0]  # 방향
result = 0  # 격자 밖으로 나간 모래의 양

for a in range(len(d)):
    # 방향 전환 시 비율 회전
    if d_idx != d[a]:
        rotate_ratio()

    d_idx = d[a]
    y += d_y[d_idx]
    x += d_x[d_idx]

    # 모래양 계산
    sand = grid[y][x]
    left = sand  # a로 이동할 모래의 양

    for j in range(5):
        for i in range(5):
            cur_y = y + j - 2
            cur_x = x + i - 2
            if ratio[j][i] == -1:  # a 위치일 경우
                a_y = cur_y
                a_x = cur_x
                continue

            add = int(sand * ratio[j][i])  # 소수점 아래 버림
            if 0 <= cur_y < N and 0 <= cur_x < N:
                grid[cur_y][cur_x] += add
            else:
                result += add
            left -= add

    grid[y][x] = 0

    # a 위치
    if 0 <= a_y < N and 0 <= a_x < N:
        grid[a_y][a_x] += left
    else:
        result += left

print(result)

 

 

실수했던 부분

---

처음에 '비율이 적혀있는 칸으로 이동하지 않은 남은 모래는 전부 𝛼로 이동한다.'는 것을 읽고,

나머지 모래 비율 55%가 𝛼로 이동하는 것으로 잘못 이해했었다.

 

이동하는 모래를 계산할 때 소수점 아래는 버리는 부분이 있기 때문에 이렇게 하면 안 되는 것이여,,,

 

 

계속 고민되는 것은 토네이도 이동 방향을 구하는 부분이다.

 

이동 방향을 0 : ← / 1 : ↓ / 2 : → / 3 : ↑ 이라고 했을 때

토네이도의 이동 방향은 '0, 1, 2, 2, 3, 3, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 ...'이다.

 

즉, 2번씩 같은 횟수로 이동한 후 횟수가 하나씩 증가하는 규칙인데, 이것을 어떻게 더 깔쌈하게 구현할 수 있을까??