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

문제

비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 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부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

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

 

출력

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

---

접근

구름의 위치를 알기위한 2차원 리스트를 생성한다. M번의 재귀호출을 통해 문제에서 주어진 조건이 구현되며 매번 NxN크기의 맵과 구름의 위치, 몇 번 호출했는지 전달한다.

해당 함수에서는 현재 구름이 있는 위치에서 이동 정보에 주어진 만큼 구름을 이동시킨다. 이때 이동한 곳의 물의 양을 1 증가시킨다.

이어서 구름이 있는 칸에서 대각선을 파악하여 4번 조건을 완성시킨다.

이후 물의 양이 2이고 현재 구름이 없는 위치의 물의 양을 2로 감소시키고 구름의 위치를 새로운 리스트에 구름의 위치를 표시한다.

위 과정 후에 재귀호출을 진행한다.

 

문제에서 주어진 조건대로 구현을 하면 되었다.

 

구현

- NxN의 맵에서 물의양과 이동 정보를 입력받는다.

- 초기 구름의 위치를 문제에서 주어진 위치로 생성한다.

- 이제 물의 양이 담긴 맵과 구름의 위치가 담긴 맵을 solve 함수에 전달한다.

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
move = [list(map(int, input().split())) for _ in range(M)]

cloud = [[0 for _ in range(N)] for _ in range(N)]
for y, x in [(N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)]:
    cloud[y][x] = 1

dy = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dx = [0, -1, -1, 0, 1, 1, 1, 0, -1]

answer = 0
solve(board, cloud, 0)
print(answer)

- 먼저 이동방향과 이동해야하는 칸 수를 빼서 d, s에 저장한다.

- 2차원 리스트를 탐색하여 해당 좌표에 구름이 있을 때 이동시키고 이동한 곳의 위치를 visited에 저장한다.

- visited을 탐색하여 해당 위치에 구름을 표시한다.

- 구름이 이동 후에 구름의 위치에서 대각선에 물이 있는지 검사하여 있는 칸 수만큼 물의 양을 증가시킨다.

- 이제 물의 양이 2이상이고 기존의 구름의 위치를 판단하여 구름이 없을 때

- 새로운 구름 배열에 1을 표시하고 해당 위치의 물의 양을 2 감소시킨다.

- 물의 양이 담긴 맵과 새로운 구름 배열을 전달한다.

def solve(board, cloud, m):
    global answer
    if m == M:
        for y in range(N):
            for x in range(N):
                answer += board[y][x]
        return

    d, s = move[m][0], move[m][1]
    visited = []
    for y in range(N):
        for x in range(N):
            if cloud[y][x] == 1:
                ny = (s * dy[d] + y) % N
                nx = (s * dx[d] + x) % N
                cloud[y][x] = 0
                visited.append((ny, nx))
                board[ny][nx] += 1

    for y, x in visited:
        cloud[y][x] = 1

    diag_y = [-1, -1, 1, 1]
    diag_x = [-1, 1, -1, 1]
    for y in range(N):
        for x in range(N):
            if cloud[y][x] == 1:
                count = 0
                for d in range(4):
                    ny = y + diag_y[d]
                    nx = x + diag_x[d]
                    if check_range(ny, nx) and board[ny][nx] > 0:
                        count += 1
                board[y][x] += count

    new_cloud = [[0 for _ in range(N)] for _ in range(N)]
    for y in range(N):
        for x in range(N):
            if board[y][x] >= 2 and cloud[y][x] == 0:
                new_cloud[y][x] = 1
                board[y][x] -= 2

    solve(board, new_cloud, m+1)

---

전체 코드

import sys
input = sys.stdin.readline

def check_range(y, x):
    return (0 <= y < N ) and (0 <= x < N)

def solve(board, cloud, m):
    global answer
    if m == M:
        for y in range(N):
            for x in range(N):
                answer += board[y][x]
        return

    d, s = move[m][0], move[m][1]
    visited = []
    for y in range(N):
        for x in range(N):
            if cloud[y][x] == 1:
                ny = (s * dy[d] + y) % N
                nx = (s * dx[d] + x) % N
                cloud[y][x] = 0
                visited.append((ny, nx))
                board[ny][nx] += 1

    for y, x in visited:
        cloud[y][x] = 1

    diag_y = [-1, -1, 1, 1]
    diag_x = [-1, 1, -1, 1]
    for y in range(N):
        for x in range(N):
            if cloud[y][x] == 1:
                count = 0
                for d in range(4):
                    ny = y + diag_y[d]
                    nx = x + diag_x[d]
                    if check_range(ny, nx) and board[ny][nx] > 0:
                        count += 1
                board[y][x] += count

    new_cloud = [[0 for _ in range(N)] for _ in range(N)]
    for y in range(N):
        for x in range(N):
            if board[y][x] >= 2 and cloud[y][x] == 0:
                new_cloud[y][x] = 1
                board[y][x] -= 2

    solve(board, new_cloud, m+1)


N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
move = [list(map(int, input().split())) for _ in range(M)]

cloud = [[0 for _ in range(N)] for _ in range(N)]
for y, x in [(N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)]:
    cloud[y][x] = 1

dy = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dx = [0, -1, -1, 0, 1, 1, 1, 0, -1]

answer = 0
solve(board, cloud, 0)
print(answer)