[BOJ] 20057 마법사 상어와 토네이도

date

Jul 29, 2023

slug

boj-20057

author

status

Public

문제 링크

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

문제

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

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

문제풀이

회오리는 항상 가운데서 일정 반시게방향으로 진행하므로 N에 따라 경로가 정해져있다. 그러므로 일단 회오리의 경로를 먼저 구해 list로 저장했고

경로에따른 회오리 프로세스를 진행시켰다.

회오리는 현재 진행방향 다음에 있는 모래들을 특정하게 이동시키는데

dx, dy테크닉을 사용하고, 현재 보는 방향 기준 왼쪽 오른쪽을 구하여 계산해야되는 리스트에 저장한 후 구했다.

만약 계산해야되는 리스트에 들어있는 x,y값이 격자 밖을 나갈경우

out에 계산값을 더하여 그 out만큼을 출력하였다.

파이썬 문제풀이 코드


import sys
input = sys.stdin.readline

arr = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
out = 0
N = int(input())

for _ in range(N):
    li = list(map(int, input().split()))
    
    arr.append(li)
    
# 회오리 진행방향

def get_tornado_directions():
    directions = [2,1,0,3]
    count = 0
    idx = 1
    target_directions = []
    while count != N**2 - 1:
        for d in range(len(directions)):
            if d == 0 or d == 1:
                for _ in range(idx):
                    target_directions.append(directions[d])
                    count+=1    
                    if count == N**2 -1:
                        return target_directions
            else:
                for _ in range(idx+1):
                    target_directions.append(directions[d])
                    count+=1
                    if count == N**2 -1:
                        return target_directions
        idx+=2            

# 회오리 프로세스 
def get_dd(left, right, straight):
    dd_list = []
    dd_list.append((dy[left]+dy[left], dx[left]+dx[left], 2))
    dd_list.append((dy[right]+dy[right], dx[right]+dx[right], 2))
    dd_list.append((dy[left], dx[left], 7))
    dd_list.append((dy[right], dx[right], 7))
    dd_list.append((dy[left]+dy[straight], dx[left]+dx[straight], 10))
    dd_list.append((dy[right]+dy[straight], dx[right]+dx[straight], 10))
    dd_list.append((dy[straight]+dy[straight], dx[straight]+dx[straight], 5))
    dd_list.append((dy[left]-dy[straight], dx[left]-dx[straight], 1))
    dd_list.append((dy[right]-dy[straight], dx[right]-dx[straight], 1))
    
    return dd_list

def tornado_process(y, x, value, d):
    global out 
    left = d-1 if d-1 >= 0 else 3
    right = d+1 if d+1 <= 3 else 0
    dd_list = get_dd(left, right, d)
    result = 0
    for ddy, ddx, p in dd_list:
        r = value*p // 100
        
        if y+ddy >= 0 and y+ddy < N and x+ddx >= 0 and x+ddx < N:
            arr[y+ddy][x+ddx] += r
        else:
            out += r
        result += r
    
    if y+dy[d] >= 0 and y+dy[d] < N and x+dx[d] >= 0 and x+dx[d] < N:
        arr[y+dy[d]][x+dx[d]] += value-result # 남은거 저장
    else:
        out += value-result
        
    arr[y][x] = 0
    
    
def tornado(y, x, d):
    next_y, next_x = y+dy[d], x+dx[d]
    value = arr[next_y][next_x]
    tornado_process(next_y, next_x, value, d)
    return next_y, next_x
    
# 시작 회오리는 정가운데 N은 홀수. 
target_directions = get_tornado_directions()
target_y, target_x = N//2, N//2

for direction in target_directions:
    target_y, target_x = tornado(target_y, target_x, direction)

print(out)

시간복잡도

O(n^2)

입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다.

예제 입력

예제 출력


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


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

알고리즘 분류

구현

시뮬레이션