BOJ - 마법사 상어와 파이어스톰 20058번 (python)

❓ 문제 - 백준 마법사 상어와 파이어스톰 20058번 - python 풀이법

 

출처 

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

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

 

 

📝 문제해결법

1. 이 문제는 구현+BFS으로 풀었다.

• 파이어스톰으로 l이 주어지면 l이 n과 같으면 격자판을 나눌 필요없이 전체 90도를 돌리고 l이 0이면 격자판이 1x1이므로 90도 회전할 필요가 없다. 또한 격자판을 나눠서 90도 회전하는 것은 rotate()함수를 사용한다.
• rotate() : 격자판을 l의 따라 나누어서 나눈 부분을 90도 회전시키기 위해 처음 board값을 b에 복사한 후 (zip()함수 사용) 회전시킨 값들을 다시 board에 그 값들을 복사한다.
• 또한 파이어스톰 후, 전체 보드 돌면서 근처에 얼음의 갯수가 3개 이상이 아니면 얼음의 양을 -1 해준다.
• 모든 파이어스톰 돈 후, 전체 얼음의 양과 bfs() 함수로 최대 얼음 덩어리의 값을 구한 후 출력한다.

2. 문제 풀면서 느낀점

• 90도 회전은 파이썬에 zip() 함수 이용하면 간단하게 해결할 수 있다.
• 격자판을 l에 따라 나누는 부분이 참 어려웠다...^^... for문으로 나눌 때 꼭, 노트에다가 인덱스 고려해서 구현할 수 있도록 하자 ^^...
• 처음의 최대 얼음 덩어리 값 구할 때 dfs로 했는데 재귀함수 횟수 걸려서 sys 모듈을 이용해야했다. 그러나 삼성역량테스트는 sys 모듈이 불가하기 때문에 bfs로 하였는데 시간이 더 절약될 수 있었다. 앞으로 bfs로 해결할 수 있으면 bfs로 구현을 먼저하자.!!!

 

💻 소스코드

# 마법사 상어와 파이어스톰 - BOJ 20058
# 구현 + BFS
import copy
from collections import deque

n, q = map(int, input().split())
nn = 2**n
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
board= [list(map(int, input().split())) for _ in range(nn)]

def rotate(l):
    b_n = 2**l
    for p1 in range(nn//b_n):
        for p2 in range(nn//b_n):
            b = []
            for i in range(b_n):
                col = []
                for j in range(b_n):
                    col.append(board[b_n*p1+i][b_n*p2+j])
                b.append(col)
            tmp = []
            for item in zip(*b):
                tmp.append(list(reversed(item)))
            for i in range(b_n):
                for j in range(b_n):
                    board[b_n*p1+i][b_n*p2+j] = tmp[i][j]

def bfs(x, y, visited):
    global max_m
    cnt = 1
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < nn and 0 <= ny < nn and not visited[nx][ny]:
                if board[nx][ny] > 0:
                    cnt += 1
                    visited[nx][ny] = True
                    q.append((nx, ny))
    max_m = max(max_m, cnt)

l_lst = list(map(int, input().split()))
for l in l_lst:
    if l == n:
        tmp = []
        b = copy.deepcopy(board)
        for item in zip(*b):
            tmp.append(list(reversed(item)))
        board = copy.deepcopy(tmp)
    elif l > 0:
        rotate(l)

    ice = [[0]* nn for _ in range(nn)]

    for i in range(nn):
        for j in range(nn):
            x, y = i, j
            cnt = 0
            if board[i][j] == 0:
                continue
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0 <= nx < nn and 0 <= ny < nn:
                    if board[nx][ny] > 0:
                        cnt += 1
            if cnt < 3:
                ice[i][j] = (board[i][j]-1)
            else:
                ice[i][j] = board[i][j]

    board = copy.deepcopy(ice)

s = 0
visited = [[False]*nn for _ in range(nn)]
max_m = 0
for i in range(nn):
    for j in range(nn):
        s += board[i][j]
        if board[i][j] != 0 and not visited[i][j]:
            bfs(i, j, visited)

print(s)
if max_m == 1:
    print(0)
else:
    print(max_m)