백준 20058 마법사 상어와 파이어스톰 (파이썬)

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

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

1. 문제의 조건대로 얼음을 한조각씩 나누고 회전한다.

   L이 0보다 크면 t에 나눈 얼음을 저장하고 list(zip(*t[::-1])) 로 90도 시계방향 회전한다.

   t에 저장한 얼음을 a로 옮겨 갱신한다

2. 얼음이 녹는것을 처리하려면 모든 얼음이 동시에 녹아야 하므로 b에 a를 복사한다.

   L이 0이면 회전을 안하므로 b에 a를 복사만 한다.

3. 인접한 칸이 범위를 벗어나지 않고 얼음이 있으면 cnt를 센다.

   cnt가 3보다 적고 b의 현재 칸에 얼음이 있으면 a에서 1을 빼 얼음을 녹인다.

4. 남은 얼음의 총합을 출력한다.

5. bfs로 탐색하면서 덩어리가 차지하는 칸의 개수를 세고, 그 중 max 값을 출력한다

from copy import deepcopy
from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

n, q = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(2 ** n)]
ll = map(int, input().split())

for l in ll:
    if l > 0:
        for i in range(0, 2 ** n, 2 ** l):
            for j in range(0, 2 ** n, 2 ** l):
                t = [a[k][j:j + 2 ** l] for k in range(i, i + 2 ** l)]
                t = list(zip(*t[::-1]))
                for x in range(2 ** l):
                    for y in range(2 ** l):
                        a[x + i][y + j] = t[x][y]
        b = deepcopy(a)
    if l == 0:
        b = deepcopy(a)

    for x in range(2 ** n):
        for y in range(2 ** n):
            cnt = 0
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if not 0 <= nx < 2 ** n or not 0 <= ny < 2 ** n:
                    continue
                if b[nx][ny] > 0:
                    cnt += 1
            if cnt < 3 and b[x][y] > 0:
                a[x][y] -= 1

ans1 = sum(sum(s) for s in a)
print(ans1)

c = [[0]*(2**n) for _ in range(2 ** n)]
q = deque()
ans2 = 0
for i in range(2 ** n):
    for j in range(2 ** n):
        if a[i][j] != 0 and c[i][j] == 0:
            q.append([i, j])
            c[i][j] = 1
            cnt = 1
            while q:
                x, y = q.pop()
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if 0 <= nx < 2 ** n and 0 <= ny < 2 ** n:
                        if a[nx][ny] != 0 and c[nx][ny] == 0:
                            cnt += 1
                            c[nx][ny] = 1
                            q.append([nx, ny])
            ans2 = max(ans2, cnt)

print(ans2)