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

Young Min Kang·2024년 2월 13일

Baek Joon

목록 보기

38/39

😲 문제

출처
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 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부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.
입력
5 4
0 0 1 0 2
2 3 2 1 0
4 3 2 9 0
1 0 2 9 0
8 8 2 1 0
1 3
3 4
8 1
4 8
출력
77

❗️ 문제 재정의

문제가 길어서 이해하는 것보다 읽는데 오래걸리는 문제이다.
구현하는 로직은 이미 위 설명에 다 들어있고 주의할 점을 보자.

맵의 시작과 끝은 연결되어 있다.
5번의 주의사항 새로운 구름은 기존 구름의 위치가 아니여야 한다.
기존 구름이 아니라는 것을 어떻게 확인할 것인가?
if 새로운 위치 in 기존 구름 으로 하면 너무 느려짐.
기존 구름을 행기준 정렬 후 앞에서부터
if i==기존구름행 and j==기존구름열로 true라면 continue

✔ 계획 수립

함수를 몇 개 만들 것인가?

이동 함수(move_cloud)
물복사 버그 함수(water_copy_bug)
새로운 구름 생성 함수(make_new_cloud)

👨🏻‍💻 문제 풀이

import sys 
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, input(). split())) for _ in range(n)]
directions = {1:(0,-1), 2:(-1,-1),3:(-1,0),4:(-1,1),5:(0,1),6:(1,1),7:(1,0),8:(1,-1)}

# 이동
clouds = [[n-1,0],[n-1,1],[n-2,0],[n-2,1]]
def move_cloud(d, s):
    dx, dy = directions[d]
    for idx, [cx, cy] in enumerate(clouds):
        nx, ny = cx + dx * s, cy + dy * s
        if nx >= n or nx < 0: nx %= n # 모듈러 연산 최소화
        if ny >= n or ny < 0: ny %= n        
        clouds[idx] = [nx, ny]
        board[nx][ny] += 1
        
# 물복사버그
def water_copy_bug():
    moves = [(1,1),(-1,-1),(1,-1),(-1,1)]
    for cx, cy in clouds:
        for dx, dy in moves:
            nx, ny = cx+dx, cy+dy
            if 0<=nx<n and 0<=ny<n and board[nx][ny]!=0:
                board[cx][cy] += 1

# 새로운 구름 생성
def make_new_cloud():
    new_cloud = []
    clouds.sort()
    for i in range(n):
        for j in range(n): # 여기서 시간 최적화 진행함.
            if len(clouds) > 0 and clouds[0][0] == i and clouds[0][1] == j:
                del clouds[0]
                continue
            if board[i][j]>=2:
                new_cloud.append([i,j])
                board[i][j] -= 2
    return new_cloud

for _ in range(m):
    d, s = map(int, input().split())
    move_cloud(d, s)
    water_copy_bug()
    clouds = make_new_cloud()

sum_water = 0
for line in board:
    sum_water+= sum(line)
print(sum_water)