[백준 21610번] 파이썬 - 마법사 상어와 비바라기

백준 21610 - 마법사 상어와 비바라기

시간 제한 1초(추가 시간 없음), 메모리 제한 1024MB

# 조건

• 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다.
• 오늘 새로 배운 마법은 비바라기이다.
• 비바라기를 시전하면 하늘에 비구름을 만들 수 있다.
• 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다.
• 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다.
• 바구니에 저장할 수 있는 물의 양에는 제한이 없다.
• (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.
• 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다.
• 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다.
  • 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.
• 비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다.
  • 구름은 칸 전체를 차지한다.
• 이제 구름에 이동을 M번 명령하려고 한다.
• i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다.
• 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다.
  • 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다.
• 이동을 명령하면 다음이 순서대로 진행된다.
  1. 모든 구름이 di 방향으로 si칸 이동한다.
  2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
  3. 구름이 모두 사라진다.
  4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
     • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
     • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
  5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
• M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

입력

• 첫째 줄에 N, M이 주어진다.
• 둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다.
• r번째 행의 c번째 정수는 A[r][c]를 의미한다.
• 다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.

출력

• 첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.

# 접근 방법

• 브루트 포스로 풀어준다.
• 처음 구름이 생성되는 칸을 0, N-1로 치환하여 clouds 리스트에 담아준다.
• 또한 before_clouds set과 di, dj 델타 리스트를 생성해주고 commands를 받아준다.
  • 이동 거리 s의 경우 N을 넘어간다면, 중복되는 경로가 생기므로 N으로 나눈 나머지로 변환하여 기록해준다.
• 로직대로 먼저 구름을 이동시킨다.
  • di[d], dj[d]에 각각 s만큼 곱한 값을 구름 위치에 더해준다.
  • 0보다 작다면 N에서 절댓값만큼 빼주고
  • N보다 크다면 N으로 나눈 나머지로 이동시키면서 temp에 추가해준다.
• 모든 이동이 끝났다면 clouds를 []로 초기화 해주고, before_clouds에 temp를 복사해준다.
• before_clouds를 순회하며 물의 양을 1씩 증가시킨 후, cross_check 함수로 4방향의 대각선에 물이 있는지 확인해준다.
  • 이 때는 경계를 넘을 수 없으므로 조심하자.
• 물이 있는 칸만큼 증가 시킨 후 모든 칸을 순회하며 물의 양이 2 이상이고 before_clouds에 들어있지 않다면 clouds에 추가해준다.

set 자료 구조를 활용한 이유는 list 보다 in => 존재 여부를 확인하는데 있어 걸이는 tat time이 작기 때문이다..!

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
import copy

'''
14:20 시작 - 14:54 solve

0번과 n-1번 연결
비바라기 시전 => (N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)에 비구름
M번 이동
왼, 왼쪽위, 위, 오른쪽위, 오른쪽, 오른쪽아래, 아래, 왼아래
1. 모든 구름이 D방향 S칸 이동
2. 구름이 있는 칸에 물 1 증가
3. 구름 제거
4. 물이 증가한 칸에 물복사  => 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 R, C의 물의 양이 증가
    이 때는 경계 넘어가는건 X
5. 물의 양이 2이상인 모든 칸에 구름 새이고, 물 2 줄어든다.
    이 때, 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
'''
def clouds_move(d, s):
    global clouds, before_clouds
    temp = set()
    for ci, cj in clouds:
        ci += di[d] * s
        cj += dj[d] * s
        if ci < 0:
            ci = N - abs(ci)
        elif ci >= N:
            ci %= N
        if cj < 0:
            cj = N - abs(cj)
        elif cj >= N:
            cj %= N
        temp.add((ci, cj))

    clouds = []
    before_clouds = temp

def increase_clouds():
    global clouds, before_clouds, arr
    for ci, cj in before_clouds:
        arr[ci][cj] += 1

    for ci, cj in before_clouds:
        num = cross_check(ci, cj)
        arr[ci][cj] += num

def cross_check(ci, cj):
    global arr
    cnt = 0
    for d in [2, 4, 6, 8]:
        ni, nj = ci + di[d], cj + dj[d]
        if 0<=ni<N and 0<=nj<N and arr[ni][nj] > 0:
            cnt += 1
    return cnt

def make_clouds():
    for i in range(N):
        for j in range(N):
            if arr[i][j] >= 2 and (i, j) not in before_clouds:
                clouds.append((i, j))
                arr[i][j] -= 2

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
clouds = [(N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)]
before_clouds = set()
di, dj = [0, 0, -1, -1, -1, 0, 1, 1, 1], [0, -1, -1, 0, 1, 1, 1, 0, -1]
commands = []
for _ in range(M):
    d, s = map(int, input().split())
    s %= N
    commands.append((d, s))

for d,s in commands:
    clouds_move(d, s)
    increase_clouds()
    make_clouds()
result = 0
for a in arr:
    result += sum(a)
print(result)