BOJ - 마법사 상어와 비바라기 21610번 (python)

❓ 문제 - 백준 마법사 상어와 비바라기 21610번 - python 풀이법

 

출처 

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

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

 

 

 

📝 문제해결법

1. 이 문제는 구현+Queue으로 풀었다.

• 초기 구름의 위치를 큐에 append한다. 
• 이동 횟수만큼 cloud로 이동한 구름 위치를 표시하고, 현재 큐에 존재하는 구름들의 위치로 방향과 거리만큼 구름을 이동시킨다. 이 때 0, n-1 행과열은 이어져 있으므로 이동할 거리는 현재위치에서 해당방향으로 이동시킨 후 n으로 나누어준다. 그리고 이동시킨 구름의 위치를 cloud에 1로 변환한다.
• 구름이 이동한 곳에 비를 뿌려 물의 양을 1증가시킨다.
• 그 후, 구름이 이동한 곳에 대각선으로 살펴서 물이 들어있는 바구니의 수를 카운트 후, 해당 숫자만큼 바구니에 물을 채워넣어준다.
• 구름이 이동한 위치를 제외하고, 모든 격자판에 물의 양이 2이상 있으면 물의 양을 2 감소시키고, 구름을 형성하여 q에 형성한 구름의 위치를 append 해준다.
• 이동횟수 m 만큼 위 과정을 반복하 후, 모든 격자판의 바구니에 들어있는 물의 양을 더해서 출력해준다.

2. 문제 풀면서 느낀점

• 오타 조심하자 제발제발제발...
• 0, n-1 의 행과 열이 이어져 있을 때 처리하는 방식을 기억하자

 

💻 소스코드

# 마법사 상어와 비바라기 - BOJ 21610
# 구현 + queue
from collections import deque

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

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

for _ in range(m):
    cloud = [[0]*n for _ in range(n)]
    d, s = map(int, input().split())
    while q:
        x, y = q.popleft()
        nx = (x + dx[d-1]*s) % n
        ny = (y + dy[d-1]*s) % n
        cloud[nx][ny] = 1

    for i in range(n):
        for j in range(n):
            if cloud[i][j] == 1:
                board[i][j] += 1

    for i in range(n):
        for j in range(n):
            if cloud[i][j] == 1:
                x, y = i, j
                cnt = 0
                for k in [1, 3, 5, 7]:
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < n and 0 <= ny < n:
                        if board[nx][ny] > 0:
                            cnt += 1
                board[x][y] += cnt

    for i in range(n):
        for j in range(n):
            if board[i][j] >= 2 and cloud[i][j] == 0:
                board[i][j] -= 2
                q.append([i, j])


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