[Python] n20057번) 마법사 상어와 토네이도

 

맵 크기 : N X N

모래 양 : A[r][c]

 

토네이도 시전 시, 가운데 칸 부터 이동이 시작된다.

토네이도는 1번에 1칸 씩 이동한다.

 

X->Y로 이동할 시,Y의 모든 모래가 비율이 적혀있는 칸과 a로 이동한다.

비율은 y에 있는 모래의 해당 비율만큼으로 소수점 아래는 버린다.

a로 이동하는 모래양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양이다.

 

모래가 이미 있는 칸으로 이동하면?모래의 양은 더해지게 된다.

 

토네이도는 (1,1)까지 이동한 뒤 소멸한다.모래가 격자 밖으로 이동할 수도 있다.토네이도 소멸 시 격자 밖으로 나간 모래양을 구해보는 것이 이 문제의 핵심

 

**제한**

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

 

 

 

---

단계 1) 토네이도 이동

좌, 하, 우, 상 순으로 이동

처음에는 모래 비율 리스트를 좌, 하, 우, 상 방향에 따라서 미리 배열에 저장해놨지만,

상당히 비효율적인 방법이라는 것을 알게 되었다.

따라서 멘토님의 가르침대로 방향 전환시 배열 회전을 해서 사용하기로 결정!

 

N=5일 경우

좌 1칸, 하 1칸, 우 2칸, 상 2칸 , 좌 3칸, 하 3칸, 우 4칸, 상4칸, 좌 4칸

1, 1, 2, 2, 3, 3, 4, 4, 4

(마지막엔 4칸 이동이 3번 반복된다)

 

이 부분은 cur=2를 이용해서 사용할 수 있는 부분!

 

2,3,4,5,6,7.... //2 -> 1,1,2,2,3,3,......

 

 

 

---

단계 2) 모래의 양 계산하기

 

소수점 부분은 날려버리기 때문에,

모래의 양을 모두 합쳐도 100%가 아닐 수 있다.

따라서 이 부분도 간과해선 안된다!

 

 

 

 

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

# 좌, 하, 우, 상
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

# 좌표가 격자 내에 위치해있는지 판단하는 함수.
def inrange(x, y):
    return y < N and y >= 0 and x >= 0 and x < N

# 모래 비율 리스트
array = [
    [0, 0, 2, 0, 0],
    [0, 10, 7, 1, 0],
    [5, 0, 0, 0, 0],
    [0, 10, 7, 1, 0],
    [0, 0, 2, 0, 0]
]

def Turn():
    tmp = [[0] * 5 for _ in range(5)]
    for i in range(5):
        for j in range(5):
            tmp[i][j] = array[i][j]
    for i in range(5):
        for j in range(5):
            array[4 - j][i] = tmp[i][j]

x = N // 2
y = N // 2
answer = 0  # 날라간 모래의 양
cur = 2
# 이동횟수를 위한 변수이다.
# 2,3,4,5,6,7....을 cur=2로 나누면 1,1,2,2,3,3,...이 나온다.
# 좌 1칸, 하 1칸, 우 2칸, 상 2칸, 좌 3칸, 3칸, 4칸 ,,, 이런식으로 이동이 이루어진다.
dir = 0  # 방향
flag = False

while True:
    cnt = cur // 2  # 이동 횟수 1,1,2,2,3,3,....
    if flag:
        cnt -= 1

    for i in range(0, cnt, 1): #좌,하 / 우,상 한 세트!
        # 좌 step // 우 step
        x += dx[dir]  # y의 좌표x 값
        y += dy[dir]  # y의 좌표y 값
        value = Map[x][y]  # y에 들어있는 값
        # y를 기준으로 해서 (0,0)이라고 가정한다.
        # (-2,-2) ~ (2,2) : 비율 범위
        for j in range(-2, 3, 1):
            for k in range(-2, 3, 1):
                if array[j + 2][k + 2] == 0:  # 값이 0이면 건너뛰기
                    continue
                curx = x + j
                cury = y + k
                curvalue = value * array[j + 2][k + 2] // 100  # 비율 계산한 값
                Map[x][y] -= curvalue  # 처음 주어진 y값에서 방금 계산한 값 빼기
                if inrange(curx, cury) == False:  # False면 격자 밖에 있는 거
                    answer += curvalue
                else:
                    Map[curx][cury] += curvalue # 격자 안에 있으면, 그 자리에 적기
        # 하 step // 상 step
        nx = x + dx[dir]
        ny = y + dy[dir]
        if inrange(nx, ny):
            Map[nx][ny] += Map[x][y]
        else:
            answer += Map[x][y]
        Map[x][y] = 0
    if flag:
        break
    cur+=1
    if cur // 2 == N:
        flag = True
    dir = (dir + 1) % 4
    Turn()

print(answer)

# 코드 출처
# https://github.com/tony9402/baekjoon/tree/main/solution/simulation

# 회전 (이건 비효율적인 코드,,)
# def Turn():
#     tmp = deepcopy(percent_list)
#     ex_tmp = deepcopy(percent_list)
#     array = [0, 0, 0, 0]
#     for k in range(4):
#         if k == 0:
#             array[k] = tmp
#             print(array)
#         else:
#             tmp = deepcopy(array[k - 1])  # deepcopy를 해야 배열의 값이 바뀌지 않는다.
#             for i in range(N):
#                 for j in range(N):
#                     ex_tmp[N - 1 - j][i] = tmp[i][j]
#             array[k] = deepcopy(ex_tmp)
#     return array
#     #좌 0, 하 1, 우 2, 상 3
#
# array=Turn()

 

---

코드 참조

github.com/tony9402/baekjoon/blob/main/solution/simulation/20057/main.cpp

tony9402/baekjoon

문제

www.acmicpc.net/problem/20057

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