[Python] 백준_마법사 상어와 파이어스톰(20058)

문제

 

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

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

 

 

풀이

 

책을 많이 안읽어서 그런지 문제 이해하는데 힘들었음.

 

일단 내가 헷갈린 부분은 먼저,

"이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다." 임.

무슨 말인가 했는데 알고보니 주변에 얼음이 3개보다 적으면 얼음이 줄어든다는 얘기였음.

 

다음은

"첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다."임.

만약 덩어리가 없으면 그냥 0만 출력하라는줄알았음. 45%에서 계속 틀려서 혹시나해서 0을 두 번 출력하도록 바꿔주니 통과됐음.

 

아무튼 이 문제에서 중요한 것은 회전인 것 같음. 마법사 시리즈는 다 회전문제같은데 풀때마다 헷갈림.

시계방향으로 90도면 x,y가 y,-x가 됨. 근데 원점 기준이므로 나도 회전을 해줄때 원점으로 옮겨서 회전시키고 다시 위치를 옮겨주었음.

이때, 각 칸이 (r,c)를 의미하지만 base를 정해줄땐 격자를 기준으로 했음. 다시말해서, 2 x 2가 있을때 [0][0]이 첫 번째 칸이 아니라 첫 번째 칸의 왼쪽 위의 좌표를 가리킨다고 생각하면됨.

 

근데 이렇게 계산하고나면, y의 좌표가 1이 더 크게나옴. 그래서 1만 빼주면 원하는대로 회전이됨. x,y가 주어지면 base의 좌표는 2^(l - 1)만큼씩 더해준 좌표가됨.

이좌표를 기준으로 회전한 뒤, temp_board에 넣고 board를 업데이트 시켜주면 l 한 번에 대한 회전이 끝남.

 

회전이 끝난 뒤엔 얼음을 제거해야함. 주변에 얼음이 3개 미만이면 얼음을 제거해주면되는데, 주의해야하는 것은 한 번에 줄여줘야함. 처음에 하나씩 지우니 1이었던 칸이 0이되고, 이로 인해 그 주변이 영향을 받아서 계속 틀렸었음.

그래서 temp_del이라는 배열에 얼음이 주는 칸들을 넣어준 뒤 한 번에 줄여주었음.

 

이렇게 계산이 다 끝나면 bfs를 이용해서 가장 큰 덩어리를 구해주기만 하면 됨.

import sys
import math
from collections import deque
input = sys.stdin.readline

n, q = map(int,input().split())
boxSize = int(math.pow(2,n))
d = [(1,0),(0,1),(-1,0),(0,-1)]
board = []
temp_board = [[0 for _ in range(boxSize)] for _ in range(boxSize)]
totalIce = 0
bigIce = 0
def rotate(x,y,l):
    global temp_board
    if l == 0:
        temp_board = board
        return
    size = int(math.pow(2,l))
    base = (x+int(math.pow(2,l - 1)), y + int(math.pow(2,l - 1)))
    for i in range(x,x+size):
        for j in range(y,y+size):
            tx = i - base[0]
            ty = j - base[1]
            nx = ty + base[0]
            ny = base[1] - tx - 1
            temp_board[nx][ny] = board[i][j]

for _ in range(boxSize):
    board.append(list(map(int,input().split())))
l_list = list(map(int,input().split()))

for l in l_list:
    for i in range(0,boxSize,int(math.pow(2,l))):
        for j in range(0,boxSize,int(math.pow(2,l))):
            rotate(i,j,l)
    board = temp_board
    temp_board = [[0 for _ in range(boxSize)] for _ in range(boxSize)]
    temp_del = [] #한번에 없애야함
    for i in range(boxSize):
        for j in range(boxSize):
            cur = (i,j)
            count = 0
            for k in range(4):
                nx = cur[0] + d[k][0]
                ny = cur[1] + d[k][1]
                if nx < 0 or ny < 0 or nx >= boxSize or ny >= boxSize:
                    continue
                if board[nx][ny] > 0:
                    count += 1
            if count < 3:
                temp_del.append((i,j))
    for point in temp_del:
        board[point[0]][point[1]] -= 1
for i in range(boxSize):
    for j in range(boxSize):
        if board[i][j] > 0:
            totalIce += board[i][j]
visited = [[False for _ in range(boxSize)] for _ in range(boxSize)]
for i in range(boxSize):
    for j in range(boxSize):
        if board[i][j] > 0 and not visited[i][j]:
            visited[i][j] = True
            queue = deque()
            queue.append((i,j))
            tempCount = 1
            while queue:
                cur = queue.popleft()
                for k in range(4):
                    nx = cur[0] + d[k][0]
                    ny = cur[1] + d[k][1]
                    if nx < 0 or ny < 0 or nx >= boxSize or ny >= boxSize:
                        continue
                    if visited[nx][ny] or board[nx][ny] <= 0:
                        continue
                    visited[nx][ny] = True
                    queue.append((nx,ny))
                    tempCount += 1
            bigIce = max(bigIce,tempCount)
if totalIce == 0 and bigIce == 0:
    print(0)
    print(0)
else:
    print(totalIce)
    print(bigIce)

 

 

_____________________________________________________________________________________________________

 

코드를 더럽게 작성한듯