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

문제 설명

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

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

문제에서 주어진 조건사항들을 그대로 구현하는 문제이다.

큰 제약사항이나 알고리즘이 따로 사용되지는 않으므로 순서에 맞게 그대로 구현만 잘 해주면 된다.

---

풀이 과정

문제에서 특별히 신경써주어야 하는 부분은, 조건5 부분이다.

 

먼저, 구름이 di 방향으로 si칸 이동한 후에 비를 뿌리고 구름은 사라진다.

이 때, 구름이 사라진 칸은 물복사 버그 후에 구름이 생길 수 없기 때문에 1로 표시해주어

해당 턴에 구름이 생길 수 없도록 해주었다.

 

그리고 그 칸에 영원히 구름이 생길 수 없는 것이 아니라,

해당 턴에만 생길 수 없기 때문에

raining 함수의 마지막 부분에 1로 표시해둔 칸을 다시 0으로 표시하여 구름이 생길 수 있도록 해주었다.

 

코드의 cloud는 현재 턴에서 처음의 구름 위치를 담은 큐이고

queue는 이 구름들을 이동시킨 후의 구름 위치이다.

from collections import deque

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

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

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


def raining(dir, dist):
    queue = deque()
    while cloud:
        a, b = cloud.popleft()
        nx = (a + dx[dir] * dist) % n
        ny = (b + dy[dir] * dist) % n
        board[nx][ny] += 1
        rain[nx][ny] = 1  # 사라진 칸은 1 표시
        queue.append((nx, ny))
        
    while queue:
        a, b = queue.popleft()
        for i in range(1, 8, 2):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if board[nx][ny] > 0:
                board[a][b] += 1

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


for i in range(m):
    d, s = map(int, input().split())
    raining(d - 1, s)

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

print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !