백준 20057 마법사 상어와 토네이도 파이썬(python)

문제

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

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

토네이도 이동 경로

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

모래가 날려서 이동하는 비율

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

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

 

입력

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

출력

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

---

풀이

[알고리즘]

문제에서 주어진 조건들을 구현하는 문제이고 문제를 풀면서 두 가지 조건이 까다로웠다. 

1. 가운데 시작하여 반시계 방향 달팽이 회전을 어떻게 구현할 건가
2. 토네이도 이동 방향에 따라 % 값이 다르게 어떻게 구현할 건가

먼저 달팽이 회전 하는 방식을 구현하기 위해 방향이 90도 회전하는 조건을 알아봤다.

달팽이 회전 구현

다음 4가지 지점에서 조건들을 가지고 회전을 하니 그때마다 회전 방향을 변경해 주도록 했다.

다음은 바라보는 방향에  따라 모래가 날리는 비율이 달라진다는 점인데 처음에는 행렬을 하나 다 저장을 할까도 생각했지만 그거보단 좌표형식으로 저장해서 사용하는 방식으로 구현을 해줬다.

방향에 따른 비율 구하기

구현 방식을 생각해 두고 그대로 문제를 따라 풀어주기만 하면 된다. 알파 지점으로 이동하는 모래는 나머지 구간에서 이동하고 나머지를 전부 이동시켜 주는 방식으로 구현하기로 했다.

[풀이 방법]

1. graph 크기 (N**2) 만큼 for문 탐색을 돌려준다. 토네이도 이동 횟수
2. 저장해 놓은 비율 index를 이용하여 move_sand 양을 구해주고 이동 후 남은 나머지를 계산하기 위해 tmp라는 변수를 두어 전체 이동 모래량 합을 구해준다. (나중에 본래 가지고 있던 것에서 빼면 그게 나머지 모래량)
3. 그래프 범위 밖으로 나가는 모래의 전체를 구하기 때문에 if 조건문으로 경계를 나가는지 따져준다.
4. 모래 이동을 마친 뒤 방향 조건에 만족하면 방향을 바꾸어 진행해 주고 그게 아니라면 같은 방향으로 계속 for문을 이어나간다. 

import sys
from collections import deque

N = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
# 바라보는 방향 ix : 왼쪽, 아래, 오른쪽, 위
ix = {
    (0, -1): 0,
    (1, 0): 1,
    (0, 1): 2,
    (-1, 0): 3
}
# 위 아래,왼,오 위위 아래아래, 앞앞, 뒤뒤, 오른 대각 위 아래, 왼 대각 위 아래
value = {
    (-1, 0): [7, 0, 7, 0],
    (1, 0): [7, 0, 7, 0],
    (0, -1): [0, 7, 0, 7],
    (0, 1): [0, 7, 0, 7],
    (-2, 0): [2, 0, 2, 5],
    (2, 0): [2, 5, 2, 0],
    (0, -2): [5, 2, 0, 2],
    (0, 2): [0, 2, 5, 2],
    (-1, 1): [1, 1, 10, 10],
    (1, 1): [1, 10, 10, 1],
    (-1, -1): [10, 1, 1, 10],
    (1, -1): [10, 10, 1, 1]
}

x, y = N // 2, N // 2
dx, dy = 0, -1
answer = 0
for _ in range(N ** 2):
    # 토네이도 다음 이동경로에 모래가 있는 경우
    nx, ny = x + dx, y + dy
    if graph[nx][ny]:
        # 토네이도 방향
        dir_index = ix[(dx, dy)]
        tmp = 0
        for k, v in value.items():
            tx, ty = k
            ttx, tty = tx + nx, ty + ny
            percentage = v[dir_index]
            move_sand = int(graph[nx][ny] * 0.01 * percentage)
            tmp += move_sand
            if 0 <= ttx < N and 0 <= tty < N:
                graph[ttx][tty] += move_sand
            else:
                answer += move_sand

        if tmp != graph[nx][ny]:
            if 0 <= nx + dx < N and 0 <= ny + dy < N:
                graph[nx + dx][ny + dy] += (graph[nx][ny] - tmp)
            else:
                answer += (graph[nx][ny] - tmp)
        graph[nx][ny] = 0
    # 방향 전환 조건
    if (N - ny - 1 == nx) or (x == y and nx > ny) or (N - nx - 1 == ny) or (nx == ny and x > y):
        dx, dy = -dy, dx
    x = nx
    y = ny

print(answer)

 

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

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