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

💡 문제 해결

1. 파이어스톰의 스펠에 따라 fire_storm함수를 호출
2. 임시 배열인 tmp_arr을 생성한 뒤 구역탐색을 시작
3. 하나의 구역에 접근할때마다 section 배열을 생성한 뒤 해당 위치에 대한 값을 저장
4. 정보입력이 완료된 section을 회전
5. 회전된 정보를 전체 임시 배열인 tmp_arr에 저장
6. 모든 section에 대한 값이 tmp_arr에 저장이 되었다면 melt함수를 실행
7. 녹은 결과를 저장할 result_arr리스트를 생성한 뒤 배열 순회
8. 해당 칸이 인접한 칸 중 얼음이 존재하는 칸이 3칸 미만이라면 해당 칸의 값을 -1한 뒤 result_arr에 저장
9. 모든 칸에 대한 갱신이 끝난 뒤 arr배열을 갱신
10. 모든 주문에 대한 처리가 끝났다면 모든 칸의 얼음의 합산 값과 가장 긴 블록을 찾아 출력

📌 pypy로 통과했다

🧾 문제 설명

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

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 
파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 
그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 
이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. 
(r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 
아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 
모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

남아있는 얼음 A[r][c]의 합
남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 
덩어리는 연결된 칸의 집합이다.

문제보기

🖨 입출력

📝 풀이

import sys


input = sys.stdin.readline
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def fire_storm(spell):
    global arr

    tmp_arr = [[0] * 2 ** N for _ in range(2 ** N)]
    for start_x in range(0, 2 ** N, spell):
        for start_y in range(0, 2 ** N, spell):
            section = [[0] * spell for _ in range(spell)]
            for i in range(spell):
                for j in range(spell):
                    section[i][j] = arr[start_x + i][start_y + j]
            section = rotate(section)
            for i in range(spell):
                for j in range(spell):
                    tmp_arr[start_x + i][start_y + j] = section[i][j]
    arr = melt(tmp_arr)
    return


def rotate(section):
    return [list(elem) for elem in zip(*section[::-1])]


def melt(tmp_arr):
    result_arr = [[0] * (2 ** N) for _ in range(2 ** N)]
    for i in range(2 ** N):
        for j in range(2 ** N):
            if tmp_arr[i][j]:
                cnt = 0
                for k in range(4):
                    nx, ny = i + dx[k], j + dy[k]
                    if 0 <= nx < 2 ** N and 0 <= ny < 2 ** N:
                        if tmp_arr[nx][ny]:
                            cnt += 1
                result_arr[i][j] = tmp_arr[i][j] - 1 if cnt < 3 else tmp_arr[i][j]

    return result_arr


def sum_ice():
    total = 0
    for i in range(2 ** N):
        for j in range(2 ** N):
            if arr[i][j]:
                total += arr[i][j]
    
    return total


def block_length():
    visited = [[False] * (2 ** N) for _ in range(2 ** N)]
    max_length = 0
    for i in range(2 ** N):
        for j in range(2 ** N):
            if arr[i][j] and visited[i][j] == False:
                visited[i][j] = True
                length = 0
                stack = [(i, j)]
                while stack:
                    x, y = stack.pop()
                    length += 1
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        if 0 <= nx < 2 ** N and 0 <= ny < 2 ** N:
                            if arr[nx][ny] and visited[nx][ny] == False:
                                visited[nx][ny] = True
                                stack.append((nx, ny))
                max_length = max(max_length, length)
    
    return max_length



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

for spell in spells:
    fire_storm(2 ** spell)

print(sum_ice())
print(block_length())

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/20058