[BOJ 백준, 삼성 SW 역량 테스트 기출 문제] 20058번 : 마법사 상어와 파이어스톰 Python, 파이썬)

www.acmicpc.net/problem/20058

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

 

DFS 함수에서 재귀가 터져서 sys.setrecursionlimit을 사용했다. 실제 삼성 코딩테스트에서는 sys 라이브러리를 사용할 수 없으니, DFS를 재귀로 짜지 않고 스택으로 짜거나 BFS로 대체하여 풀어야 할 듯 하다.

 

회전하는 부분을 제대로 구하지 못해서 다른 블로그 글을 참조했다. 리스트의 회전은 어렵다..

 

 

소스코드

import sys, copy
sys.setrecursionlimit(10 ** 5)
dy = [-1,1,0,0]
dx = [0,0,-1,1]

visited = set()

def maxIce(y, x):    
    visited.add((y, x))
    ret = 1
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if 0<= ny < 2**N and 0 <= nx < 2**N:
            if (ny, nx) not in visited and board[ny][nx] > 0:
                ret += maxIce(ny, nx)   
    return ret

def melt():
    melt_ice = []
    for y in range(2**N):
        for x in range(2**N):
            ice = 0
            if board[y][x] == 0: 
                continue
            for k in range(4):
                ny = y + dy[k]
                nx = x + dx[k]
                if 0 <= ny < 2**N and 0 <= nx < 2**N :
                    if board[ny][nx] >= 1:
                        ice += 1
            if ice < 3:
                melt_ice.append([y, x])
    
    for y, x in melt_ice:
        board[y][x] -= 1
    return

def rotate(L):
    global board
    K = 2**L
    for i in range(0,2**N, K):
        for j in range(0, 2**N, K):
            new_board = [board[r][j:j+K] for r in range(i, i+K)]
            for y in range(K):
                for x in range(K):
                    board[i+x][j+K-1-y] = new_board[y][x]                
    return

N, Q = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(2**N)]
magic = list(map(int, input().split()))

for L in magic:
    rotate(L)
    melt()

# 남아있는 얼음의 총합
sumOfIce = 0
for i in range(2**N):
    for j in range(2**N):
        sumOfIce += board[i][j]

# 남아있는 얼음 중 가장 큰 덩어리가 차지 하는 칸의 개수
maxOfCnt = 0
cnt = 0
for y in range(2**N):
    for x in range(2**N):        
        if (y, x) not in visited and board[y][x] > 0:   
            maxOfCnt = max(maxOfCnt, maxIce(y, x))

print(sumOfIce)
print(maxOfCnt)