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

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

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

설명

• 토네이도를 시전하면 격자의 가운데 칸 부터 토네이도의 이동이 시작. 
• 토네이도는 한 번에 한 칸 이동한다. 
• 토네이도가 한 칸 이동할 때마다 모래는 일정한 비율로 흩날리게 된다. 
• x에서 y로 이동하면, y의 모든 모래가 비율과 a가 적혀 있는 칸으로 이동한다. 
• 비율이 적혀 있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다.
• a로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양이다. 

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

처음에 격자 밖으로 모래가 이동할 수 있다는 말이 이해가 가지 않았었는데, 다음과 같은 뜻임을 알 수 있었다. 예를들어, 토네이도가 x에서 y로(왼쪽으로) 이동할 때, y에 있던 모래가 이동하는 배열을 다음과 같다. 또한 토네이도가 아래로 이동할 때 비율 배열 모양은 다음과 같다.

출처: https://velog.io/@kongji47

또한 다음 그림을 통해 격자 밖으로 모래가 나갈 수 있음을 이해할 수 있다. 따라서 방향별 모래 비율 위치는 다음과 같이 이해할 수 있다.

핵심 아이디어

• 토네이도 회전 방향(y위치)
• 방향별 모래 비율 위치
• a값과 격자 밖의 모래의 양

출처: https://velog.io/@kongji47

토네이도 이동 방향: 좌 -> 하 -> 우 -> 상

토네이도가 직선으로 이동하는 거리는 좌,하 / 우,상 이렇게 2세트로 나눠져 세트마다 1씩 증가한다. 그림을 보면 알 수 있듯이 왼쪽 아래방향에 대해서는 홀수번 만큼 진행하고, 오른쪽 위방향에 대해서는 짝수번 만큼 진행하게 된다. 따라서 for loop를 돌면서 i가 홀수라면 왼쪽 아래쪽으로 퍼지게끔, 짝수라면 오른쪽 위쪽으로 퍼지게끔 함수를 실행해주면 된다. 몇 퍼센트의 모래가 퍼질것인지에 대해서는 미리 좌표와 퍼센트를 저장해놓아야하고, 각 방향에 따라 다르게 설정해줘야한다.

• x에서 y로 이동하면, y의 모든 모래가 비율과 a가 적혀 있는 칸으로 이동한다. 

left = [(-2,0,0.02),(2,0,0.02), (-1,-1,0,1),(1,-1,0.1),(-1,1,0.01),(1,1,0.01),
	(-1,0,0.07), (1,0,0.07), (0,-2,0.05),(0,-1,0)
] # 왼쪽 방향으로 퍼지는 경우

오른쪽 방향으로 퍼지는 경우 x와 y좌표를 반대로, 아래쪽 방향으로 퍼질때, 그리고 위쪽 방향으로 퍼질 때는 아래쪽 x,ㅛ좌표와 교환!

right = [(x,-y) for x,y,z in left] # 오른쪽
down = [(-y,x,z) for x,y,z in left] # 아래
up = [(y,x,z) for x,y,z, in left]

for i in range(n+1):
	if i % 2: # 홀수라면
    	move(i, 0,-1,left) # 왼쪽
        move(i, 1, 0,down) # 아래
    else: # i가 짝수 일때
    	move(i, 0, 1, right) # 오른쪽
        move(i, -1, 0, up) #위

 

move 함수: 현재 좌표를 업데이트하고, 해당 좌표에 대해서 퍼지는 모래양을 계산해주면된다. 미리 설정해 놓은 비율로 계산을 하되, 범위가 벗어나면 정답값에 누적하여 더해주고, 범위안에 들어오면 해당 좌표의 모래값을 업데이트 해주면 된다. 회오리 돌다가 끝날 수도 있으므로 현재 좌표의 x좌표나 y좌표가 0보다 작게되면 탐색 종료! 퍼지는 모래들 이외에 현재 자리에 퍼지지 않은 모래양을 계산하기 위해서는 퍼지는 모래의 누적값을 계산해 주어야한다.

# 모래 계산하는 함수
def move(time, dx, dy, direction):
    global ans, s_x, s_y

    # y좌표 계산 & x좌표 갱신
    for _ in range(time):
        s_x += dx # s_x = s_x + dx
        s_y += dy # 현재 y좌표에서 dy만큼 이동
        if s_y < 0 or s_x < 0:  # 범위 밖이면 stop
            break

        # 3. a, out_sand
        total = 0  # a 구하기 위한 변수 , 총 퍼지 모래의 양
        for dx, dy, z in direction:
            nx = s_x + dx
            ny = s_y + dy
            if z == 0:  # a(나머지)
                new_sand = graph[s_x][s_y] - total
            else:  # 비율
                new_sand = int(graph[s_x][s_y] * z)

            if 0 <= nx < N and 0 <= ny < N:   # 인덱스 범위이면 값 갱신
                graph[nx][ny] += new_sand # 현재 모래에서 누적해서 더함
            else:  # 범위 밖이면 ans 카운트
                ans += new_sand
            total += new_sand

코드 구현

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

# 2. 방향별 모래 비율 위치
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]
down = [(-y, x, z) for x, y, z in left]
up = [(y, x, z) for x, y, z in left]

s_x, s_y = N//2, N//2  # 시작좌표
ans = 0  # out_sand
# 모래 계산하는 함수
def move(time, dx, dy, direction):
    global ans, s_x, s_y

    # y좌표 계산 & x좌표 갱신
    for _ in range(time):
        s_x += dx # s_x = s_x + dx
        s_y += dy # 현재 y좌표에서 dy만큼 이동
        if s_y < 0 or s_x < 0:  # 범위 밖이면 stop
            break

        # 3. a, out_sand
        total = 0  # a 구하기 위한 변수 , 총 퍼지 모래의 양
        for dx, dy, z in direction:
            nx = s_x + dx
            ny = s_y + dy
            if z == 0:  # a(나머지)
                new_sand = graph[s_x][s_y] - total
            else:  # 비율
                new_sand = int(graph[s_x][s_y] * z)

            if 0 <= nx < N and 0 <= ny < N:   # 인덱스 범위이면 값 갱신
                graph[nx][ny] += new_sand # 현재 모래에서 누적해서 더함
            else:  # 범위 밖이면 ans 카운트
                ans += new_sand
            total += new_sand
# 1.토네이도 회전 방향(y위치)
for i in range(1, N + 1):
    if i % 2: # i가 홀수 일 때,
        move(i, 0, -1, left) # 왼쪽으로 i번 이동
        move(i, 1, 0, down) # 아래로 i번 이동
    else: # i가 짝수일 때
        move(i, 0, 1, right) # 오른쪽으로 i번 이동
        move(i, -1, 0, up) # 위로 i번 이동

print(ans)