마법사 상어와 토네이도 (20057번) - 백준 (BOJ)

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

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

 

백준 - 마법사 상어와 토네이도 (20057번)

 

난이도 : Gold 3

알고리즘 : Simulation

풀이 소요 시간 : 90분

Time Complexity : O( N^2 )

문제집 : 삼성 SW 역량 테스트 기출 문제

 

import sys
input = sys.stdin.readline


def scatter(d, r, c):
    dr, dc = drr[d], dcc[d]
    sand = board[r][c]
    update(r+(2*dr), c+(2*dc), sand//20)
    update(r+dr+dc, c+dc+dr, sand//10)
    update(r+dr-dc, c+dc-dr, sand//10)
    update(r+(2*dc), c+(2*dr), sand//50)
    update(r-(2*dc), c-(2*dr), sand//50)
    update(r+dc, c+dr, sand*7//100)
    update(r-dc, c-dr, sand*7//100)
    update(r-dr+dc, c-dc+dr, sand//100)
    update(r-dr-dc, c-dc-dr, sand//100)
    sand -= sand//20 + (sand//10 + sand//50 + sand//100 + sand*7//100)*2
    update(r+dr, c+dc, sand)
    board[r][c] = 0
    return


def update(r, c, amount):
    global out
    if 0 <= r < N and 0 <= c < N:
        board[r][c] += amount
    else:
        out += amount
    
        
if __name__ == '__main__':
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    out = d = 0
    r = c = N>>1
    drr = [0, 1, 0, -1]
    dcc = [-1, 0, 1, 0]
    for i in range(1, N):  # 2
        for _ in range(2):  # 2
            for _ in range(i):  # 2
                r += drr[d]
                c += dcc[d]
                scatter(d, r, c)  # 1
            d = (d+1)%4
    for _ in range(N-1):  # 2
        r += drr[d]
        c += dcc[d]
        scatter(d, r, c)  # 1
    print(out)

 

구현 그 자체인 문제였다.

 

# 1.

방향에 상관없이 모래를 일관적으로 흩뿌리는 기능을 구현하기가 정말 까다로웠다.

 

처음엔 동서남북 따로따로 코드를 4개 만들까도 생각했지만, 이러면 코드가 너무 길어질 것 같았다.

 

좀 더 고민하다보니, 방향 전환에도 일반적으로 적용할 수 있는 indexing 방법이 떠올랐고

그대로 구현할 수 있었다.

 

 

# 2.

토네이도의 회전 부분은 규칙성을 찾아서 구현했다.

 

(1, 1, 2, 2, 3, 3, ..., N-1, N-1, N-1)

 

1부터 N-2까지 각 숫자마다 방향이 2번씩 바뀌고,

마지막 N-1에서는 3번 바뀌는게 보였다.

 

그 로직대로 구현했다.