[Gold V] 마법사 상어와 비바라기 - 21610

문제 링크

성능 요약

메모리: 35068 KB, 시간: 196 ms

분류

구현, 시뮬레이션

문제 설명

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 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번째 이동 명령은 방향 d_i과 거리 s_i로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

1. 모든 구름이 d_i 방향으로 s_i칸 이동한다.
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개의 줄에는 이동의 정보 d_i, s_i가 순서대로 한 줄에 하나씩 주어진다.

출력

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

---

문제 풀이

이 코드는 "마법사 상어와 비바라기" 문제의 파이썬 정답 코드로, N x N 격자에서 M번의 비구름 이동 및 물복사버그 마법을 시뮬레이션하여 최종 물의 양의 합을 구하는 문제입니다.

문제 분석

문제는 N x N 크기의 격자에서 바구니에 담긴 물의 양을 M번의 이동 명령에 따라 변화시키는 시뮬레이션을 요구합니다. 초기에는 (N, 1), (N, 2), (N-1, 1), (N-1, 2) (1-based 인덱스) 위치에 비구름이 생성됩니다. 각 이동 명령은 방향 d와 거리 s로 구성되며, 다음 5단계가 순서대로 진행됩니다:

1. 구름 이동: 모든 구름이 d 방향으로 s칸 이동합니다. 이때 격자 경계를 넘어가면 반대편으로 연결됩니다 (예: N행 아래는 1행).
2. 물 증가: 각 구름이 있는 칸의 바구니 물의 양이 1 증가합니다.
3. 구름 소멸: 모든 구름이 사라집니다.
4. 물복사버그: 2단계에서 물이 증가한 칸 (r, c)에 대해, 대각선 방향으로 거리가 1인 칸 중 물이 있는 바구니의 수만큼 (r, c)의 물의 양이 추가로 증가합니다. 이때는 경계를 넘어가지 않습니다.
5. 새 구름 생성: 물의 양이 2 이상인 모든 칸에 구름이 다시 생기고, 해당 칸의 물의 양은 2 줄어듭니다. 단, 3단계에서 구름이 사라진 칸은 제외됩니다.

M번의 이동이 모두 끝난 후, 모든 바구니에 저장된 물의 양의 총합을 출력하는 것이 최종 목표입니다.

접근 방법

이 문제는 주어진 규칙에 따라 정확히 시뮬레이션하는 전형적인 구현 문제입니다.

1. 격자 표현: N x N 격자는 2차원 리스트 board로 나타냅니다.
2. 구름 관리: 구름의 위치는 튜플 (r, c)를 원소로 가지는 리스트 cloud로 관리합니다. 각 이동마다 cloud 리스트를 갱신합니다.
3. 방향 벡터: 8방향 이동 및 4방향 대각선 탐색을 위한 미리 정의된 방향 벡터 배열 (dirx, diry, directions)을 사용합니다.
4. 경계 처리: 구름 이동 시 경계 연결은 (좌표 + 이동량) % N 연산을 사용하여 구현합니다. 물복사버그 마법 시 경계 미연결은 0 <= r < N 및 0 <= c < N 조건을 통해 처리합니다.
5. 구름 사라진 칸 제외: 5단계에서 새로운 구름을 생성할 때, 3단계에서 사라진 구름이 있던 칸을 제외해야 합니다. 이를 효율적으로 처리하기 위해 직전 단계의 구름 위치를 set 자료구조(cloud_set)에 저장하여 빠르게 포함 여부를 확인합니다.

구현 설명

1. 초기 설정 및 입력 처리

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.
• 8방향 이동을 위한 dirx, diry 배열을 정의합니다. (문제의 1부터 8 방향을 0부터 7 인덱스로 매핑하기 위해 코드에서는 d-1로 접근).
• N, M을 입력받고, board (물의 양), ops (이동 명령)을 초기화합니다.
• 초기 구름 위치인 (N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1) (0-based 인덱스)를 cloud 리스트에 추가합니다.
• 물복사버그 마법을 위한 대각선 4방향 directions를 정의합니다.

2. M번의 이동 시뮬레이션

주어진 M번의 이동 명령에 대해 for 루프를 돌며 각 단계를 함수로 구현하여 호출합니다.

• 구름 이동 (move 함수):

  • 현재 cloud 리스트의 각 구름 (x, y)에 대해 이동 명령 d, s를 적용합니다.
  • dx = dirx[d-1] * s, dy = diry[d-1] * s를 계산하여 이동할 총 거리를 구합니다. d-1은 문제의 18 방향을 07 인덱스로 맞추기 위함입니다.
  • 새로운 구름 위치는 ((x + dx) % n, (y + dy) % n)로 계산됩니다. % n 연산을 통해 격자 경계를 넘어가는 경우 반대편으로 연결되는 효과를 얻습니다.
  • 새로운 구름들의 위치를 담은 new_cloud 리스트를 반환합니다. 이 new_cloud가 다음 cloud가 됩니다.
  • 이동 후 cloud를 set으로 변환한 cloud_set은 직전에 구름이 있었던 모든 칸을 나타내며, pluswater와 newcloud 단계에서 활용됩니다.

• 물 증가 및 물복사버그 (pluswater 함수):

  • cloud 리스트의 각 구름 (x, y)에 대해 board[x][y]의 물의 양을 1 증가시킵니다.
  • 이후 다시 cloud 리스트를 순회하며 각 (x, y) 칸에 대해 물복사버그 마법을 시전합니다.
  • 대각선 4방향 directions에 대해 이웃한 칸 (sx, sy)를 확인합니다.
  • 0 <= sx < n 이고 0 <= sy < n 조건을 통해 격자 경계를 넘어가지 않는 대각선 칸만 검사합니다.
  • if (board[sx][sy] or (sx,sy) in cloud_set): 조건으로 (sx, sy) 칸에 물이 있는지를 확인합니다. board[sx][sy]는 현재 시점의 물의 양을, (sx,sy) in cloud_set은 해당 칸이 이동 후 구름이 위치한 칸(따라서 곧 물이 1 증가할 칸)인지를 나타냅니다. 이 둘 중 하나라도 참이면 물이 있는 것으로 간주하여 board[x][y]의 물의 양을 1 추가합니다.

• 새로운 구름 생성 (newcloud 함수):

  • N x N 격자의 모든 칸 (i, j)를 순회합니다.
  • board[i][j] >= 2이고, (i, j)가 직전 구름이 사라진 칸(cloud_set에 포함되지 않는)이 아닌 경우에만 새로운 구름으로 인정합니다. (if (i,j) in cloud_set: continue를 통해 제외).
  • 해당 칸의 물의 양을 board[i][j] -= 2 감소시키고, (i, j)를 new_cloud 리스트에 추가합니다.
  • 이 new_cloud 리스트가 다음 이동의 cloud가 됩니다.

3. 최종 물의 양 합산

M번의 이동이 모두 끝난 후, board의 모든 칸을 순회하며 board[i][j]에 저장된 물의 양을 합산하여 answer에 저장하고 출력합니다.

⏱복잡도 분석

• 시간 복잡도:
  • 초기화 및 입력: O(N^2) (보드 입력) + O(M) (이동 명령 입력) = O(N^2 + M).
  • M번의 시뮬레이션 루프:
    • move 함수: 현재 구름의 수 K에 비례합니다. 최악의 경우 K = N^2이므로 O(N^2).
    • pluswater 함수: K개의 구름 각각에 대해 4방향을 확인합니다. 최악의 경우 O(K * 4) = O(N^2).
    • newcloud 함수: N x N 격자 전체를 순회하며 set (cloud_set) 확인(O(1))을 수행합니다. O(N^2).
  • 따라서 M번의 이동 총 시간 복잡도는 M * (O(N^2) + O(N^2) + O(N^2)) = O(M * N^2).
  • N=50, M=100의 경우, 100 * 50^2 = 100 * 2500 = 250,000으로 충분히 효율적입니다.
• 공간 복잡도:
  • board: N x N 격자를 저장하므로 O(N^2).
  • ops: M개의 이동 명령을 저장하므로 O(M).
  • cloud 및 new_cloud: 최대 N^2개의 구름 위치를 저장할 수 있으므로 O(N^2).
  • cloud_set: 최대 N^2개의 구름 위치를 저장할 수 있으므로 O(N^2).
  • 총 공간 복잡도는 O(N^2 + M). N=50, M=100의 경우 50^2 + 100 = 2500 + 100으로 메모리 제한을 초과하지 않습니다.

핵심 포인트

1. 경계 연결 mod 연산: 구름 이동 시 1번 행/열의 위/왼쪽이 N번 행/열이고 N번 행/열의 아래/오른쪽이 1번 행/열이 되는 경계 연결 특성을 (좌표 + 이동량) % N 연산으로 정확하게 구현해야 합니다.
2. set을 이용한 효율적인 구름 제외: 새로운 구름 생성 시 직전에 구름이 사라진 칸을 제외해야 하는 조건((i,j) in cloud_set)을 set 자료구조를 활용하여 O(1) 시간에 빠르게 판별하는 것이 중요합니다.
3. 물복사버그 조건의 정확한 해석: 물복사버그 마법에서 "물이 있는 바구니"를 판단할 때, 대각선 칸의 현재 물의 양(board[sx][sy])뿐만 아니라, 해당 칸이 현재 이동으로 인해 곧 물이 1 증가할 구름 칸이었는지((sx,sy) in cloud_set)까지 고려해야 문제의 의도에 부합합니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

#dir 0,1,2,3,4,5,6,7
dirx = [0, -1, -1, -1, 0, 1, 1, 1]
diry = [-1, -1, 0, 1, 1, 1, 0, -1]

n,m= map(int,input().split())
board = []
for i in range(n):
    board.append(list(map(int, input().split())))

ops = []
for i in range(m):
    ops.append(list(map(int, input().split())))

cloud = []
cloud.append((n-1,0))
cloud.append((n-1,1))
cloud.append((n-2,0))
cloud.append((n-2,1))

def move(op, cloud):
    d,s = op
    dx,dy = dirx[d-1] * s, diry[d-1] * s

    new_cloud = []
    for x,y in cloud:
        new_cloud.append(((x+dx)%n, (y+dy) %n))

    return new_cloud

directions = [(-1,-1),(-1,1),(1,1),(1,-1)]
def pluswater(cloud, cloud_set):
    for x,y in cloud:
        board[x][y] += 1

        for dx,dy in directions:
            sx,sy = x+dx,y+dy
            if 0<=sx<n and 0<=sy<n and (board[sx][sy] or (sx,sy) in cloud_set):
                board[x][y] += 1

def newcloud(cloud, cloud_set):
    new_cloud = []
    for i in range(n):
        for j in range(n):
            if board[i][j] >= 2:
                if (i,j) in cloud_set:
                    continue
                board[i][j] -= 2
                new_cloud.append((i,j))

    return new_cloud

for i in range(m):
    cloud = move(ops[i], cloud)
    cloud_set = set(cloud)
    pluswater(cloud,cloud_set)
    cloud = newcloud(cloud, cloud_set)

answer = 0
for i in range(n):
    answer += sum(board[i])
print(answer)