이번 문제는 삼성 기출 문제로, 시뮬레이션 구현과 BFS를 이용하여 해결하였다. 구현에 쉽게 접근하기 위해 각 기능을 함수로 따로 구현하였다.

• cycle: 얼음의 위치를 돌리는 함수
• melt: 얼음을 녹이는 함수
• find_biggest: 가장 큰 얼음 덩어리를 찾는 함수
• get_ice: 얼음의 전체 크기 합을 구하는 함수

함수의 작성까지는 크게 어렵지 않았지만, 함수를 호출하는 과정에서 길을 잃어 시간을 많이 소모하였다. 내가 구현한 cycle 함수의 경우에는, 현재 위치와 현재의 범위를 기준으로 테두리만 회전시키게 된다. 그렇기 때문에 내부에 모든 라인을 회전시키기 위해서는 여러 번 호출해서 회전을 시켜야 하는데, 2**3부터는 2**2와 2보다 더 크게 차이나기 때문에 몇번을 더 호출해줘야 했다. 결과를 계속해서 출력해보고, 코드를 계속해서 확인하며 이 실수를 찾을 수 있었고, 문제를 해결하였다.

Code

import copy
from collections import deque
n, q=map(int, input().split())
a=[list(map(int, input().split())) for _ in range(2**n)]
l=list(map(int, input().split()))
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
v=[[False for _ in range(2**n)] for _ in range(2**n)]
def cycle(y, x, l_size):
    for i in range(l_size-1):
        tmp[y+i][x+l_size-1]=a[y][x+i]
        tmp[y+l_size-1][x+l_size-1-i]=a[y+i][x+l_size-1]
        tmp[y+l_size-1-i][x]=a[y+l_size-1][x+l_size-1-i]
        tmp[y][x+i]=a[y+l_size-1-i][x]
def melt():
    global a
    tmp_a=copy.deepcopy(a)
    for i in range(2**n):
        for j in range(2**n):
            cnt=0
            if a[i][j]>0:
                for k in range(4):
                    ni, nj=i+dy[k], j+dx[k]
                    if 0<=ni<2**n and 0<=nj<2**n and a[ni][nj]>0:
                        cnt+=1
                if cnt<3:
                    tmp_a[i][j]-=1
    a=copy.deepcopy(tmp_a)
def find_biggest(y, x):
    q=deque()
    q.append((y, x))
    v[y][x]=True
    result=1
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<2**n and 0<=nx<2**n and a[ny][nx]>0 and not v[ny][nx]:
                result+=1
                v[ny][nx]=True
                q.append((ny, nx))
    return result
def get_ice():
    result=0
    for i in range(2**n):
        for j in range(2**n):
            result+=a[i][j]
    return result
for ls in l:
    tmp = [[0 for _ in range(2 ** n)] for _ in range(2 ** n)]
    if ls==0:
        melt()
    else:
        for i in range(0, 2**n-(2**ls-1), 2**ls):
            for j in range(0, 2**n-(2**ls-1), 2**ls):
                c=0
                while c*2!=2**ls:
                    cycle(i+c, j+c, 2**ls-(c*2))
                    c+=1
        a=copy.deepcopy(tmp)
        melt()
ice=get_ice()
big_ice=0
for i in range(2**n):
    for j in range(2**n):
        if not v[i][j] and a[i][j]>0:
            big_ice=max(big_ice, find_biggest(i, j))
print(ice)
print(big_ice)