[BOJ 20057 🥇3] 마법사 상어와 토네이도(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

예제 입력 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

예제 출력 1 

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

예제 출력 2

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

예제 출력 3

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

예제 출력 4

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

예제 출력 5

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

예제 출력 6

22961

 

⭕ CODE

# wind[0] -> 왼쪽 wind[1] -> 아래 wind[2] -> 오른쪽 wind[3] -> 위
wind = [
    [(0, -2, 0.05), (-1, -1, 0.1), (1, -1, 0.1), (-2, 0, 0.02), (2, 0, 0.02), (-1, 0, 0.07), (1, 0, 0.07), (1, 1, 0.01),
     (-1, 1, 0.01)],
    [(2, 0, 0.05), (1, -1, 0.1), (1, 1, 0.1), (0, 2, 0.02), (0, -2, 0.02), (0, 1, 0.07), (0, -1, 0.07), (-1, 1, 0.01),
     (-1, -1, 0.01)],
    [(0, 2, 0.05), (-1, 1, 0.1), (1, 1, 0.1), (-2, 0, 0.02), (2, 0, 0.02), (-1, 0, 0.07), (1, 0, 0.07), (-1, -1, 0.01),
     (1, -1, 0.01)],
    [(-2, 0, 0.05), (-1, -1, 0.1), (-1, 1, 0.1), (0, 2, 0.02), (0, -2, 0.02), (0, 1, 0.07), (0, -1, 0.07), (1, 1, 0.01),
     (1, -1, 0.01)]]

# 방향
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]


def sand(x, y, d):
    # 그 자리에 있던 모래양
    here = arr[x][y]
    # 바람이 불어서 날아가야하므로 arr[x][y]를 0으로 바꿔준다.
    arr[x][y] = 0

    # α값을 계산해주기위한 zz
    zz = 0

    # 바람이 불면 흩어지는 9방향에 대해서
    for i in range(9):
        nx = x + wind[d][i][0]
        ny = y + wind[d][i][1]

        # 격자 안에 존재 한다면
        if 0 <= nx < n and 0 <= ny < n:
            # 그 위치에 그 비율만큼 곱해서 더해준다
            # int()를 함으로서 소수점 아래 버리기
            arr[nx][ny] = int(arr[nx][ny] + here * wind[d][i][2])

            # α값을 계산하기 위해서 흩어져간 모래양을 더해준다
            zz += int(here * wind[d][i][2])
        # 격자 밖으로 떨어져 나간 모래도 더해준다
        else:
            zz += int(here * wind[d][i][2])

    # α의 위치
    nx = x + dx[d]
    ny = y + dy[d]

    # 격자안에 존재한다면
    if 0 <= nx < n and 0 <= ny < n:
        # 그자리에 있던 모래양에서 흩어져나간 모래양을 추가로 더해준다
        arr[nx][ny] += here - zz


n = int(input())

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

# 처음 존재하는 모래양에서 나중에 바람이 다 불고 남은 모래양을 빼면
# 격자 밖으로 나간 모래양을 구할 수 있다.
total_sand = 0
for i in range(n):
    for j in range(n):
        total_sand += arr[i][j]

# 토네이도가 움직이는 거리를 담을 리스트
tornado = []
# 토네이도는 같은 거리를 두번씩 움직인다.
for i in range(1, n):
    tornado.append(i)
    tornado.append(i)
# 마지막은 n-1만큼가서 (0,0)으로 간다.
tornado.append(n - 1)

# [1, 1, 2, 2, 3, 3, 4, 4, 4]

# 중앙 위치
x, y = n // 2, n // 2

# 방향을 정할 d
d = 0

for i in tornado:
    count = 0
    while count < i:
        # 다음 위치
        x += dx[d]
        y += dy[d]
        count += 1
        # 다음구역에 모래가 있다면
        if arr[x][y] > 0:
            sand(x, y, d)
    # 방향
    d = (d + 1) % 4

# 바람이 다 지나가고 난 후 모래양을 구한다
total = 0
for i in range(n):
    for j in range(n):
        total += arr[i][j]

print(total_sand - total)

✏️ Comment

단순 구현인데 시간이 엄청 걸렸다. α값을 처음에 0.55만큼이라고 생각하고 계산하여 예시와 다른 정답이 나왔다. α값을 제대로 이해하였다면 빠르게 문제해결이 가능했을 것 같다.

 

• 문제이해가 가장 중요하다. 문제를 꼼꼼히 읽고 이해하는 습관을 기르자