한걸음

[220925] 백준 20058 : 마법사 상어와 파이어스톰 본문

Coding Test

[220925] 백준 20058 : 마법사 상어와 파이어스톰

우당탕탕 할 수 있다!!! 2022. 9. 25. 22:06
반응형

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

 

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

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c

www.acmicpc.net

1. 보드판 일부 떼어내서 회전시키기

 다음과 같은 3 x 3 형태의 배열을 생각해보자

시계 방향으로 90도 회전할 경우 1행의 정보는 3열로 이동할 것이고, 3행의 정보는 1열로 이동할 것이다. 따라서, 배열의 마지막 행부터 불러와서 temp 배열에 append 해주면 90도 시계방향으로 회전한 것과 같은 효과를 볼 수 있다. 

def rotate(arr):
    temp = [[] for _ in range(len(arr))]
    for row in range(len(arr)-1, -1, -1): # 한 행을 불러와서
        for col in range(len(arr[row])-1, -1, -1) :
            # 아래서 부터 채운다. 위에서 부터 채워도 상관없다.
            temp[col].append(arr[row][col])
    return temp

매번 배열을 불러올 때, 시작점과 끝점들을 기록해두었다가 회전한 이후에 다시 보드판에 업데이트하면 된다.

rot_arr = []
for i in range(0, 2**N, 2**L):
    temp_arr = board[i : i + 2**L]
    for j in range(0, 2**N, 2**L) :
        for k in temp_arr :
            rot_arr.append(k[j : j + 2**L])
        x0, x1, y0, y1 = int(i), int(i + 2**L), int(j), int(j + 2**L)
        rot_arr = rotate(rot_arr)
        ix, iy = 0, 0
        for xxx in range(x0, x1):
            iy = 0
            for yyy in range(y0, y1):
                board[xxx][yyy] = rot_arr[ix][iy]
                iy += 1
            ix += 1
            if ix >= abs(x1 - x0) : ix = 0
        rot_arr = []

2. 얼음 줄이기

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

 

말을 참 어렵게 해 놨다. 이해하기 쉽게 표현하면,

 

"자기 위치에서 상하좌우 인접한 칸에 얼음이 2개 이하일 경우에 얼음이 감소한다."

 

정도로 해석이 가능할 것 같다. (한편으로는 보드판 경계 밖을 고려해서 이렇게 말한 것 같기도 하다.)

※ 주의! ※ 

여기서 이미 얼음 다 녹아서 없어졌는데, 무작정 -1 하는 일은 없도록 하자

3. 전체 코드

메모리 : 123796 KB, 시간 : 1016ms, 풀이 시간 : 102분

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

# 북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def rotate(arr):
    temp = [[] for _ in range(len(arr))]
    for row in range(len(arr)-1, -1, -1): # 한 행을 불러와서
        for col in range(len(arr[row])-1, -1, -1) :
            # 아래서 부터 채운다. 위에서 부터 채워도 상관없다.
            temp[col].append(arr[row][col])
    return temp

def diminish():
    temp = []
    for i in range(2**N):
        for j in range(2**N):
            x, y = i, j
            cnt = 0
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if 0 <= nx < 2**N and 0 <= ny < 2**N and board[nx][ny] > 0 :
                    cnt += 1
            if cnt < 3 :
                temp.append([x, y])
    while temp :
        x, y = temp[0]
        del temp[0]
        if board[x][y] > 0 :
            board[x][y] -= 1

def bfs():
    # 가장 큰 덩어리 찾기
    visited = [[False for _ in range(2**N)] for _ in range(2**N)]
    maxValue = 0
    for i in range(2**N):
        for j in range(2**N):
            if board[i][j] > 0 and not visited[i][j] :
                q = [[i, j]]
                visited[i][j] = True
                cnt = 1
                while q :
                    x, y = q[0]
                    del q[0]
                    for d in range(4):
                        nx = x + dx[d]
                        ny = y + dy[d]
                        if 0 <= nx < 2 ** N and 0 <= ny < 2 ** N and not visited[nx][ny] :
                            if board[nx][ny] > 0 :
                                cnt += 1
                                visited[nx][ny] = True
                                q.append([nx, ny])
                maxValue = max(maxValue, cnt)
    return maxValue

def solve():
    it = 0
    while it < Q :
        L = L_info[it]
        rot_arr = []
        for i in range(0, 2**N, 2**L):
            temp_arr = board[i : i + 2**L]
            for j in range(0, 2**N, 2**L) :
                for k in temp_arr :
                    rot_arr.append(k[j : j + 2**L])
                x0, x1, y0, y1 = int(i), int(i + 2**L), int(j), int(j + 2**L)
                rot_arr = rotate(rot_arr)
                ix, iy = 0, 0
                for xxx in range(x0, x1):
                    iy = 0
                    for yyy in range(y0, y1):
                        board[xxx][yyy] = rot_arr[ix][iy]
                        iy += 1
                    ix += 1
                    if ix >= abs(x1 - x0) : ix = 0
                rot_arr = []
        diminish()
        it += 1
    total = 0
    for i in range(2**N):
        total += sum(board[i])
    result = bfs()
    print(total)
    print(result)
solve()

 

반응형