[백준 20057번] 마법사 상어와 토네이도 - python

문제 링크

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

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

 

풀이 

문제 이해가 잘 안돼서 애먹은 .. 

1. 중앙에서부터 시작하는 토네이도 이동 규칙은 다음과 같다. 

왼쪽 1번 -> 아래 1번 -> 오른쪽 2번 -> 위 2번 > 왼쪽 3번 -> 아래 3번 ... 

따라서 홀수번째 일 때 왼쪽, 아래 이동 시 모래 양을 계산해주었고

짝수번째 일 때 오른쪽, 위 이동 시 모래 양을 계산해주었다. 

 

2. 방향에 따른 모래 비율을 저장해주었다.

left, right, down, up 배열에 방향 별 현재 위치에서 이동 위치까지의 상대적 인덱스 차이와 함께, 이동 위치의 비율을 저장해주었다.

(dx, dy, 비율) 

 

3. 이동 시 모래 계산은 다음과 같다. 

1) 1번에서 구한 이동 횟수만큼 방향에 맞게 이동시켜주며 현재 위치를 갱신한다. 

- y 가 0 보다 작다면, 토네이도 이동이 끝난 것이므로 종료하면 된다. 

2) 2번에서 기록해둔 현재 방향에 따른 모래 이동 위치 및 비율에 따라 이동할 모래양 new_sand를 구한다. 

현재 위치의 모래양 * 비율 

3-1) 모래 이동 위치가 범위를 벗어나지 않는다면, 모래를 이동시킨다. 

3-2) 모래 이동 위치가 범위를 벗어난다면, ans 에 더한다. -> 구하고자 하는 값 

4) 마지막 방향에는 a의 상대적 위치를 넣어, 위에서 이동시킨 모래양을 원래 있던 양에서 뺀 값을 구하고 3)번을 수행한다. 

 

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

def count(cnt, dx, dy, direct):
    global ans, x, y
    
    # 현재 위치 갱신 
    for _ in range(cnt):
        x += dx
        y += dy 
        
        # 이동 종료 
        if y < 0 :
            break 
            
        # 이동한 전체 양 
        total = 0 
        
        for dx, dy, z in direct:
            nx = x + dx 
            ny = y + dy 
            
            if z == 0 :
                new_sand = graph[x][y] - total
            else :
                new_sand = int(graph[x][y] * z)
                total += new_sand
                
            if 0<= nx < n  and 0 <= ny < n:
                graph[nx][ny] += new_sand 
            else :
                ans += new_sand 
                
n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))
    
# 방향 별 이동 위치와 비율 저장 
left = [(1, 1, 0.01), (-1, 1, 0.01), (1, 0, 0.07), (-1, 0, 0.07), (1, -1, 0.1),
         (-1, -1, 0.1), (2, 0, 0.02), (-2, 0, 0.02), (0, -2, 0.05), (0, -1, 0)]
# 오른쪽으로 이동할 때 
right = [ (x, -y, z) for x, y, z in left]
# 위로 이동할 때 
up = [(y,x,z) for x,y,z in left]
# 아래로 이동할 때 
down = [ (-y,x,z) for x, y, z in left]

x = n //2 
y = n //2 
ans = 0
for i in range(1, n+1):
    # 홀수 일 때 왼쪽, 아래 이동 
    if i % 2 != 0 :
        # (이동 횟수, dx, dy, 방향 전달 )
        count(i, 0, -1, left)
        count(i, 1, 0, down)
    # 짝수 일 때 오른쪽, 위 이동
    else :
        count(i, 0, 1, right)
        count(i, -1, 0, up)

print(ans)