마법사 상어와 파이어 스톰 [삼성 기출]

1. 문제 접근 방법

- 격자판을 나누어서, 격자판을 회전시킨 후에, 얼음의 양을 줄이는 것을 반복하는 문제이다. 

  이 때 중요한 것은 격자판을 정확하게 회전시키는 것이다. 

-> rotate 함수에 주목하자

-> rotate 함수에서 4차원 for문을 활용해서 회전을 시켰다. 

 

 

2. 내 코드

from collections import deque 
import copy

N, Q = map(int, input().split())

board = [] 

for i in range(2**N):
    row = list(map(int, input().split()))
    board.append(row)
    
magics = list(map(int, input().split()))

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

biggestIce = 0
iceCnt = 0 

visited = [[False]*(2**N) for _ in range(2**N)]


def rotate(N, L):
    
    global board
    
    N = 2**N 
    L = 2**L 
    
    tmpBoard = copy.deepcopy(board)
    
    for x in range(0, N, L):
        for y in range(0, N, L):
            for i in range(L):
                for j in range(L):
                    board[x+j][y+L-i-1] = tmpBoard[x+i][y+j]
                    
    
def melt():
    
    global board
    
    tmpBoard = [[0]*(2**N) for _ in range(2**N)]    
    
    for i in range(0, 2**N):
        for j in range(0, 2**N):
            ice = board[i][j] 
            cnt = 0 
            
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                
                if 0<=nx and nx < 2**N and 0<=ny and ny<2**N:
                    if board[nx][ny] > 0:
                        cnt += 1 
                else:
                    continue
                
            
            if cnt >= 3:
                tmpBoard[i][j] = ice
                continue
            else:
                if ice >= 1:
                    tmpBoard[i][j] = ice - 1 
                
                
    board = copy.deepcopy(tmpBoard)
            
            
            
def getIceSum():
    
    sum = 0 
    
    for i in range(0, 2**N):
        for j in range(0, 2**N):
            sum += board[i][j] 
            
            
    return sum 
    


for L in magics:
    rotate(N, L)
    melt()
    

total = getIceSum()


def bfs(x, y, visited):
    
    global iceCnt 
    
    visited[x][y] = True
    iceCnt += 1
    q = deque()
    q.append([x,y])
    
    while q:
        x, y = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx and nx<2**N and 0<=ny and ny<2**N and board[nx][ny] != 0 and visited[nx][ny] == False:
                visited[nx][ny] = True
                iceCnt += 1 
                q.append([nx, ny])
    


for i in range(2**N):
    for j in range(2**N):
        if board[i][j] != 0 and visited[i][j] == False:
            iceCnt = 0 
            bfs(i, j, visited)
            biggestIce = max(biggestIce, iceCnt)


    
print(total) 
print(biggestIce)