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

문제

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법을 시전하기 전	L = 1	L = 2

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

출력

첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

제한

• 2 ≤ N ≤ 6
• 1 ≤ Q ≤ 1,000
• 0 ≤ A[r][c] ≤ 100
• 0 ≤ Li ≤ N

---

L을 기준으로 격자를 90도씩 돌리고, 보드의 각 요소들에 대해 상하좌우 네 방향을 탐색하며 얼음을 녹여주면 된다. 큰 덩어리가 차지하는 칸의 개수는 bfs나 dfs로 칸의 개수를 세고, 최대값을 갱신해주면 되는 간단한 문제이다.

리뷰시 보드를 90도 회전할 때 굳이 new_board를 리턴하지 않는 방법을 보면 되겠다.

from collections import deque

# 서,남,동,북
dRow = [0,1,0,-1]
dCol = [-1,0,1,0]

N,Q = map(int,input().split())
N = 2**N
board = [[0]*(N+2)]
for _ in range(N):
    board.append([0] + list(map(int,input().split())) + [0])
board.append([0]*(N+2))
L = list(map(int,input().split()))


def rotate_cw_90(mat,n,row,col):
    for x in range(n):
        for y in range(n):
            board[row+x][col+y] = mat[n-y-1][x]


for q in range(Q):
    # 격자 돌리기
    step = 2**L[q]
    for row in range(1,N+1,step):
        for col in range(1,N+1,step):
            mat = [[board[r][c] for c in range(col,col+step)] for r in range(row,row+step)]
            rotate_cw_90(mat,step,row,col)
    # 얼음 녹이기
    new_board = [[*elem] for elem in board]
    for row in range(1,N+1):
        for col in range(1,N+1):
            if board[row][col] > 0:
                cnt = 0
                for i in range(4):
                    nRow,nCol = row+dRow[i],col+dCol[i]
                    if board[nRow][nCol] == 0:
                        cnt += 1
                    if cnt >= 2:
                        new_board[row][col] -= 1
                        break
    board = [[*elem] for elem in new_board]

sum_value = 0
for row in range(1,N+1):
    for col in range(1,N+1):
        sum_value += board[row][col]
print(sum_value)

max_value = 0
visited = [[0]*(N+2) for _ in range(N+2)]
for row in range(1,N+1):
    for col in range(1,N+1):
        if board[row][col] > 0 and visited[row][col] == 0:
            cnt = 1
            visited[row][col] = 1
            q = deque()
            q.append((row,col))
            while q:
                r,c = q.popleft()
                for i in range(4):
                    nr,nc = r+dRow[i],c+dCol[i]
                    if board[nr][nc] > 0 and visited[nr][nc] == 0:
                        visited[nr][nc] = 1
                        cnt += 1
                        q.append((nr,nc))
            if cnt > 1:
                max_value = max(max_value,cnt)
print(max_value)