[백준] 21610_마법사 상어와 비바라기 (Python)

📕 문제

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

21610번: 마법사 상어와 비바라기

 

💡 풀이법

1. 먼저 구름의 첫 위치의 좌표들을 clouds라는 deque에 담는다.

2. clouds를 돌면서 구름을 이동시킨 값을 다시 clouds에 넣는다. 이동시킨 자리에 위치한 칸의 물의 양을 1씩 증가 시켜준다.

(이와 동시에 모두 0으로 채워진 N x N 의 격자 칸 is_clouds를 만들어서 구름이 있는 칸은 1로 바꿔준다.

3. 그 다음 다시 clouds를 돌면서 구름이 있는 칸의 대각선에 위치한 칸들을 확인하고 물이 있는 칸의 수(cnt)를 세서 구름이 있는 칸에 cnt를 더한다.

4. N x N의 격자를 돌면서 물이 2 이상이고 구름이 없는 칸을 new_clouds라는 deque에 담는다.

5. 위의 과정을 이동 횟수만큼 반복한다.

6. 마지막에 격자 안에 있는 숫자(물의 양)를 모두 더한다.

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dxy1 = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]
dxy2 = [(-1, 1),(1, -1),(1, 1),(-1, -1)]
clouds = deque([(N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)])

for _ in range(M):
    d, c = map(int, sys.stdin.readline().split())
    is_cloud = [[0]*N for _ in range(N)]
    for _ in range(len(clouds)):
        x, y = clouds.popleft()
        dx, dy = dxy1[d-1]
        nx, ny = (x + dx*c)%N, (y + dy*c)%N
        board[nx][ny] += 1
        clouds.append((nx, ny))
        is_cloud[nx][ny] = 1
    
    for cloud in clouds:
        x, y = cloud
        cnt = 0
        for dx, dy in dxy2:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny]:
                cnt += 1
        board[x][y] += cnt

    new_clouds = deque()
    for i in range(N):
        for j in range(N):
            if board[i][j] >= 2 and not is_cloud[i][j]:
                board[i][j] -= 2
                new_clouds.append((i, j))

    clouds = new_clouds

total = 0
for i in range(N):
    total += sum(board[i])

print(total)