구현, BFS - 20058번: 마법사 상어와 파이어스톰

import sys
from collections import deque

input = sys.stdin.readline

n, q = map(int, input().split())
maps = []
for i in range(0, pow(2, n)):
    line = list(map(int, input().split()))
    maps.append(line)

magic_list = list(map(int, input().split()))

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


# 얼음 덩어리 크기 세는 함수
def bfs(x, y, maps, visited):
    # set()초기화는 무조건 빈 상태로 해서 .add()로 원소 추가해야함!!! 처음부터 넣지 않기
    union = set()
    union.add((x, y))
    queue = deque([(x, y)])
    visited[x][y] = True

    while queue:
        x, y = queue.popleft()
        for i in range(0, 4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 맵 내부에 있고 얼음이 있고 현재 union에 없는 곳이라면 방문
            if (
                0 <= nx < n_2
                and 0 <= ny < n_2
                and maps[nx][ny] > 0
                and not visited[nx][ny]
            ):
                queue.append((nx, ny))
                union.add((nx, ny))
                visited[nx][ny] = True

    return len(union)


# magic_list를 돌면서 l을 얻어서 몇칸 씩 회전할지 구하기
for l in magic_list:
    n_2 = pow(2, n)
    l_2 = pow(2, l)

    melt_place = []

    # l = 0이면 회전은 패스 가능함!
    if l > 0:
        for i in range(0, n_2, l_2):
            for j in range(0, n_2, l_2):
                """
                mini_mat = []
                for k in range(l_2):
                    mini_mat.append(maps[i + k][j : j + l_2])

                # 미니 격자를 시계방향으로 90도 회전시키기
                turn_90_mat = []
                transpose_mat = list(zip(*mini_mat))  # 행렬 전치
                for line in transpose_mat:
                    reverse_line = list(line)
                    reverse_line.reverse()
                    turn_90_mat.append(reverse_line)
                """
                # 코드 최적화
                mini_mat = [maps[i + k][j : j + l_2] for k in range(l_2)]
                turn_90_mat = [list(reversed(col)) for col in zip(*mini_mat)]

                # 회전된 격자를 맵에 적용
                for k in range(l_2):
                    maps[i + k][j : j + l_2] = turn_90_mat[k]

    # 모든 격자를 회전시킨 후
    # 모든 칸을 순회하면서 상하좌우에 얼음 3개이상 붙어있는 덩어리가 있는지 체크
    for i in range(0, n_2):
        for j in range(0, n_2):
            # 얼음 없는 칸이면 패스
            if maps[i][j] == 0:
                continue
            ice_cnt = 0
            for k in range(0, 4):
                nx, ny = i + dx[k], j + dy[k]

                if 0 <= nx < n_2 and 0 <= ny < n_2 and maps[nx][ny] != 0:
                    ice_cnt += 1
            # 주변 얼음이 3칸 미만이면 녹이기
            if ice_cnt < 3 and maps[i][j] > 0:
                # 지금 녹이지 말고 한번에 녹여야 함 주의!!!
                melt_place.append([i, j])

    # 전체 맵 순회 후 한번에 얼음 녹이기
    for i in range(0, len(melt_place)):
        x, y = melt_place[i]
        maps[x][y] -= 1

visited = []
for i in range(0, n_2):
    visited.append([False] * n_2)

max_size = 0
total_ice = 0
# 모든 마법이 끝난 후, 남아있는 전체 얼음의 양과 가장 큰 얼음 덩어리 칸 개수 구하기
for i in range(0, n_2):
    for j in range(0, n_2):
        total_ice += maps[i][j]

        # 얼음이 존재하고, 아직 방문하지 않은 곳이라면 bfs호출 (얼음 존재할때만 부르기)
        if maps[i][j] > 0 and not visited[i][j]:
            ice_size = bfs(i, j, maps, visited)
            # 최대 얼음 크기 갱신
            if max_size < ice_size:
                max_size = ice_size

print(total_ice)
print(max_size)