[백준 20058] 마법사 상어와 파이어스톰

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

20058번: 마법사 상어와 파이어스톰

---

접근

이번 문제에서는 특정 범위를 90도로 회전시키는 것을 구현하는 것이 가장 큰 문제였다. 먼저 board라는 원본 맵을 탐색하면서 입력받은 범위만큼 나누고 90도로 회전시키는 함수에 회전한 board를 다른 2차원 리스트에 저장하였다.

일단 1이 들어왔다고 가정하고 몇몇 범위를 예시로 어떻게 인덱스가 변하는지 파악하였다. 예를 들어 (0, 0)을 시작으로 2x2크기는 (0, 0) -> (0, 1) , (0, 1) -> (1, 1), (1, 0) -> (0, 0), (1, 1) -> (1, 0)으로 변했으며 (2, 4)에서 2x2는 (2, 4) -> (2, 5), (2, 5) -> (3, 5), (3, 4) -> (2, 4), (3, 5) -> (3, 4)으로 변하였다.

 

위에서 변하는 것을 어떻게 구현할지 생각했을 때 회전한 맵의 x는 (y시작점 + x 시작점 + 크기) - y - 1로 할 수 있었고 y는 y의 시작점을 기준으로 x가 증가할 때 같이 증가시켜주었다. 

이렇게 90도 회전만 구현하면 다른 것은 큰 문제가 되지 않았다.

 

구현

- 입력받은 범위를 기준으로 각각의 범위를 회전시킨다.

- rotate함수에서 회전을 시킨 값을 rotated_board에 저장한다.

    rotated_board = [[0 for _ in range(2**N)] for _ in range(2**N)]
    for y in range(0, 2**N - 2**L + 1, 2**L):
        for x in range(0, 2**N - 2**L + 1, 2**L):
            rotate(y, x, 2**L)

def rotate(n, m, size):
    for y in range(n, n+size):
        idx = n
        for x in range(m, m+size):
            rotated_board[idx][(n+m+size) - (y+1)] = board[y][x]
            idx += 1

- 회전이 모두 끝났다면 주위에 얼음이 3개 미만인 곳을 찾아서 큐에 넣는다.

- 큐에서 좌표를 하나씩 꺼내어 해당 좌표의 얼음 양을 1씩 감소한다.

- 이때 큐를 사용하는 이유는 모든 얼음들이 동시에 1씩 감소하기 때문이다. 만약 순서대로 탐색하면서 얼음의 양을 감소시키면 3개의 미만이 되는 것이 더 생길 수도 있다.

    q = deque()
    for y in range(2**N):
        for x in range(2**N):
            if rotated_board[y][x] > 0:
                count = 0
                for d in range(4):
                    ny = y + dy[d]
                    nx = x + dx[d]
                    if check_range(ny, nx) and rotated_board[ny][nx] > 0:
                        count += 1
                if count < 3:
                    q.append((y, x))

    while q:
        y, x = q.popleft()
        rotated_board[y][x] -= 1

    board = rotated_board

- 이제 board를 탐색하면서 최종 얼음의 양을 더해나가고

- bfs를 통해 가장 넓은 얼음 구역을 구한다.

total = 0
max_area = 0
visited = [[False for _ in range(2**N)] for _ in range(2**N)]
for y in range(2**N):
    for x in range(2**N):
        if board[y][x] > 0:
            total += board[y][x]
            max_area = max(max_area, bfs(y, x))

print(total)
print(max_area)

---

전체 코드

import sys
from collections import deque

input = sys.stdin.readline

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

def rotate(n, m, size):
    for y in range(n, n+size):
        idx = n
        for x in range(m, m+size):
            rotated_board[idx][(n+m+size) - (y+1)] = board[y][x]
            idx += 1

def bfs(y, x):
    q = deque()
    q.append((y, x))
    visited[y][x] = True
    count = 0
    while q:
        cy, cx = q.popleft()
        count += 1
        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and visited[ny][nx] == False and board[ny][nx] > 0:
                q.append((ny, nx))
                visited[ny][nx] = True

    return count

def show(board):
    for y in range(2**N):
        for x in range(2**N):
            print(board[y][x], end=' ')
        print()
    print()

N, Q = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(2**N)]
cmd = list(map(int, input().split()))

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
for L in cmd:
    rotated_board = [[0 for _ in range(2**N)] for _ in range(2**N)]
    for y in range(0, 2**N - 2**L + 1, 2**L):
        for x in range(0, 2**N - 2**L + 1, 2**L):
            rotate(y, x, 2**L)
    q = deque()
    for y in range(2**N):
        for x in range(2**N):
            if rotated_board[y][x] > 0:
                count = 0
                for d in range(4):
                    ny = y + dy[d]
                    nx = x + dx[d]
                    if check_range(ny, nx) and rotated_board[ny][nx] > 0:
                        count += 1
                if count < 3:
                    q.append((y, x))

    while q:
        y, x = q.popleft()
        rotated_board[y][x] -= 1

    board = rotated_board

total = 0
max_area = 0
visited = [[False for _ in range(2**N)] for _ in range(2**N)]
for y in range(2**N):
    for x in range(2**N):
        if board[y][x] > 0:
            total += board[y][x]
            max_area = max(max_area, bfs(y, x))

print(total)
print(max_area)