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

풀이 시간

• 1h 3m

구현 방식

• 부분 격자로 나누기
  -> 회전을 2^L * 2^L크기의 부분 격자 단위로 해주어야하기 때문에 range(0, 2N, 2L[q])만큼의 2중 for문을 돌면서 시작 i점과 시작 j점을 구함
  -> 시작 i점과 시작 j점을 기준으로 step만큼 (row의 길이만큼) for문을 돌면서 col 리스트를 완성시킴
  -> 해당 col 리스트가 부분 격자이기 때문에 해당 리스트를 시계방향으로 90도 회전시켜주면 됨

• 배열 회전
  -> 시계방향 90도 회전: col = reversed(col); list(map(list, zip(*col)))
  -> (배열 회전 관련 내용은 여기를 참고)

• 얼음 녹이기
  -> ice 배열을 0으로 초기화해서 만들어주고 그냥 board를 순회하며 조건에 맞게 얼음을 녹여주고 해당위치의 얼음 값을 ice에 할당해주면 됨
  -> 순회를 마친 후 ice 리스트의 값들을 board에 복사

• bfs로 얼음 덩어리 탐색
  -> 그냥 visit 리스트를 이용해서 bfs 탐색을 하며 칸의 개수를 구해주고 이를 최댓값으로 갱신해줌

코드

import sys
from collections import deque

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

def bfs(x, y):
    queue = deque([]); queue.append((x, y))
    visit[x][y] = True
    local_max_space = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < 2**N and 0 <= ny < 2**N:
                if board[nx][ny] != 0 and not visit[nx][ny]:
                    visit[nx][ny] = True
                    queue.append((nx, ny))
                    local_max_space += 1
    
    return local_max_space


N, Q = map(int, sys.stdin.readline()[:-1].split())
board = [] # 각 칸 별 얼음의 양
for n in range(2**N):
    board.append(list(map(int, sys.stdin.readline()[:-1].split())))
L = list(map(int, sys.stdin.readline()[:-1].split())) # Q번의 단계

for q in range(Q): #단계 수행
    step = 2**L[q]

    for i in range(0, 2**N, step): #회전
        row = board[i:i+step]; semi_boards = []
        for j in range(0, 2**N, step):
            col = []
            for s in range(step):
                col.append(row[s][j:j+step])
            col = reversed(col)
            semi_board= list(map(list, zip(*col)))
            for x in range(step):
                for y in range(step):
                    board[i+x][j+y] = semi_board[x][y]
    
    ice = [[0] * 2**N for _ in range(2**N)]
    for x in range(2**N): #얼음 녹이기
        for y in range(2**N):
            if board[x][y] != 0:
                cnt = 0
                for i in range(4):
                    nx = x + dx[i]; ny = y + dy[i]
                    if 0 <= nx < 2**N and 0 <= ny < 2**N:
                        if board[nx][ny] > 0: cnt += 1
                if cnt < 3:
                    ice[x][y] = board[x][y] - 1
                else:
                    ice[x][y] = board[x][y]
    board = ice.copy()

total = 0; max_space = 0
visit = [[False] * 2**N for _ in range(2**N)]
for i in range(2**N):
    for j in range(2**N):
        total += board[i][j]
        if board[i][j] != 0 and not visit[i][j]:
            max_space = max(max_space, bfs(i, j))

print(total)
print(max_space)

결과