[Python] 백준 20057 마법사 상어와 토네이도

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

# 20057 마법사 상어와 토네이도

def tornado(r, c, direction):
    out_value = 0
    temp_grounds = list()
    dir1 = direction
    dir2 = dir1 + 1
    dir3 = dir1 + 2
    dir4 = dir1 + 3
    dir2 %= 4
    dir3 %= 4
    dir4 %= 4

    cur_value = grounds[r][c]

    count_dirt = 0
    value1 = cur_value * 1 // 100
    value2 = cur_value * 2 // 100
    value5 = cur_value * 5 // 100
    value7 = cur_value * 7 // 100
    value10 = cur_value * 10 // 100
    # 좌측 기준
    # 위 한 칸
    cr = r + dr[dir2]
    cc = c + dc[dir2]
    if 1 <= cr <= N and 1 <= cc <= N:
        temp_grounds.append([cr, cc, value7])
    else:
        out_value += value7
    count_dirt += value7

    # 위 앞칸
    kr = cr + dr[dir1]
    kc = cc + dc[dir1]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value10])
    else:
        out_value += value10
    count_dirt += value10

    # 위 뒤칸
    kr = cr + dr[dir3]
    kc = cc + dc[dir3]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value1])
    else:
        out_value += value1
    count_dirt += value1

    # 위 위 칸
    kr = cr + dr[dir2]
    kc = cc + dc[dir2]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value2])
    else:
        out_value += value2
    count_dirt += value2

    # 아래 한 칸
    cr = r + dr[dir4]
    cc = c + dc[dir4]
    if 1 <= cr <= N and 1 <= cc <= N:
        temp_grounds.append([cr, cc, value7])
    else:
        out_value += value7
    count_dirt += value7

    # 아래 앞칸
    kr = cr + dr[dir1]
    kc = cc + dc[dir1]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value10])
    else:
        out_value += value10
    count_dirt += value10

    # 아래 뒤칸
    kr = cr + dr[dir3]
    kc = cc + dc[dir3]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value1])
    else:
        out_value += value1
    count_dirt += value1

    # 아래 아래 칸
    kr = cr + dr[dir4]
    kc = cc + dc[dir4]
    if 1 <= kr <= N and 1 <= kc <= N:
        temp_grounds.append([kr, kc, value2])
    else:
        out_value += value2
    count_dirt += value2

    # 앞 앞칸
    cr = r + dr[dir1] * 2
    cc = c + dc[dir1] * 2
    if 1 <= cr <= N and 1 <= cc <= N:
        temp_grounds.append([cr, cc, value5])
    else:
        out_value += value5
    count_dirt += value5

    # 바로 앞칸
    cr = r + dr[dir1]
    cc = c + dc[dir1]
    temp_vaiue = cur_value - count_dirt
    if 1 <= cr <= N and 1 <= cc <= N:
        temp_grounds.append([cr, cc, temp_vaiue])
    else:
        out_value += temp_vaiue

    grounds[r][c] = 0
    for tr, tc, t_value in temp_grounds:
        grounds[tr][tc] += t_value

    return out_value


# 좌 하 우 상
dr = [0, 1, 0, -1]
dc = [-1, 0, 1, 0]

N = int(input())
grounds = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]

temp_r = N // 2 + 1
temp_c = N // 2 + 1

result = 0
# 한 칸씩 움직임
num = 1
direction = 0
while 0 < temp_r <= N and 0 < temp_c <= N:
    direction %= 4
    for _ in range(num):
        temp_r += dr[direction]
        temp_c += dc[direction]
        if temp_c == 0 or temp_r == 0:
            break
        # 토네이도 작업
        result += tornado(temp_r, temp_c, direction)

    direction += 1
    if direction % 2 == 0:
        num += 1

print(result)

헤맨 부분

일단, 문제가 이해가 가지 않았다.
알파(a)에 어떤 값이 들어가는지 잘 모르겠어서, 질문 게시판을 쭉 읽어보았다.
55%로 하면 될 것 같았는데, 나눗셈을 할 때 나머지로 나누어 떨어지는 값들까지 모두 고려하여 a에 넣어야 하는 것이었다.

소용돌이치며 이동하는 것을 구현하는 것도 처음엔 고통이었는데, 예전에 비슷한 문제를 푼 적이 있어 생각보단 빠르게 구현해냈다.

tornado를 구현한 뒤 제출했을 때, 시간 초과가 발생했다.

또다시 무너진 순두부멘탈. 질문 게시판에도 시간 초과 관련 게시글은 없었고, 구글링을 통해 약간의 힌트를 얻을 수 있었다.

N=500이므로, N^2 = 250,000이다. (N <= 499지만 편의상 500으로 하자)

내 기존 코드는, tornado 함수 안에서도 N*1, N*1 크기를 가진 temp_grounds를 만들었었다.

temp_grounds를 정의해준 뒤, 전체 r과 c를 돌며 덧셈을 해주었다.

N=500일 때, 이미 코드의 하단에서 temp_r, temp_c를 찾으며 빙글빙글 돌며 250,000개의 연산이 발생한다. 여기에서 temp_grounds가 또 250,000번의 연산을 해주면, 어마어마한 연산 숫자가 발생한다.

통상적으로 python에서 1초에 1억 번의 연산이 가능하다고 한다.
100^4 = 10,000^2 = 100,000,000으로, 100을 4제곱했을 때의 연산 숫자이다.
나는 500을 4제곱했으므로, 1억이 훌쩍 넘는 연산을 하였고, 시간 초과가 나는 것이다.

해법을 얻은 뒤, temp_grounds를 단순 리스트 형식으로 처리했으며, 조건이 맞을 때의 r, c, value를 입력받고 마지막에 이를 더해줌으로써 처리하였다.

실전에서 시간 초과가 발생했으면 아찔했을 것 같다. 검색을 했지만, 잘 극복해내서 다행이다.