[Python/BOJ] 20058. 마법사 상어와 파이어스톰

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

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

문제

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 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가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

출력

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

풀이

Code

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

def solution(n, _, graph, command) :
    # 1. 회전 함수 정의
    def rotate(x, y, size) :
        global graph
        # 1-1. 서브 그래프 생성
        sub_graph = [line[:] for line in graph]
        # 1-2. 90도 회전
        for i in range(x, x + size) :
            for j in range(y, y+size) :
                # 1-2-1. (x, y)을 (0, 0)으로 옮겨주는 작업 수행
                ox, oy = i - x, j - y
                # 1-2-2. 변환된 위치에서 90도 회전
                rx, ry = oy, size - ox - 1
                # 1-2-3. 다시 x, y을 더해줌으로써 변동된 위치에 원래 값 입력
                graph[rx + x][ry + y] = sub_graph[i][j]

    # 2. 마법 시전 함수 정의
    def magic(x, y, size, L) :
        # 2-1. 원하는 범위에 들어왔을 경우
        if size == 2 ** L :
            # 회전 함수 실행
            rotate(x, y, size)
            return
        # size 재설정
        size //= 2
        # 분할정복
        magic(x, y, size, L)
        magic(x, y + size, size, L)
        magic(x + size, y, size, L)
        magic(x + size, y + size, size, L)
    # 3. 얼음 갯수 감소 함수 생성
    def reduction() :
        # 3-1. 서브 그래프 생성
        sub_graph = [line[:] for line in graph]
        # 3-2.
        for x in range(l) :
            for y in range(l) :
                if graph[x][y] == 0 : continue
                cnt = 0
                # 4방향 얼음 여부 카운트
                for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
                    nx, ny = x + dir_x, y + dir_y
                    # 맵을 벗어나거나 얼음이 아닐 경우 카운트
                    if nx < 0 or nx >= l or ny < 0 or ny >= l or sub_graph[nx][ny] <= 0 : continue
                    cnt += 1
                # 얼음이 있는 칸 3개 또는 그 이상과 인접해 있지 않다면 얼음의 양 감소
                if cnt < 3 : graph[x][y] -= 1


    # 4. 얼음 덩어리를 찾기 위한 bfs 함수 정의
    def bfs(x, y) :
        # 4-1. 큐 생성 후 현재 위치 삽입
        queue = deque()
        queue.append((x, y))
        # 4-2. 현재 위치 방문 처리
        visited[x][y] = True
        cnt = 1
        # 4-3.
        while queue :
            # 위치 인덱스 반환
            x, y = queue.popleft()
            for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
                nx, ny = x + dir_x, y + dir_y
                # 예외처리
                if nx < 0 or nx >= l or ny < 0 or ny >= l : continue
                # 얼음이 존재하면서 방문하지 않은 경우
                if graph[nx][ny] and not visited[nx][ny] :
                    # 카운팅
                    cnt += 1
                    # 방문 처리
                    visited[nx][ny] = True
                    # 큐에 다음 위치 삽입
                    queue.append((nx, ny))
        # 4-4. 얼음 덩어리 반환
        return cnt
    # 5. 길이 변수 생성
    l = 2 ** n
    # 6.
    for L in command :
        if l != 2**L :
            # 파이어스톰 실행
            magic(0, 0, l, L)
        # 얼음 갯수 줄이기
        reduction()
    # 7. 남아있는 얼음의 합 출력
    summation = sum([sum(line) for line in graph])
    print(summation)
    # 8. 가장 큰 덩어리 찾기
    max_cnt = 0
    visited = [[False for _ in range(l)] for _ in range(l)]
    for i in range(l) :
        for j in range(l) :
            if graph[i][j] and not visited[i][j] :
                cnt = bfs(i, j)
                # 최댓값 업데이트
                max_cnt = max(max_cnt, cnt)
    # 9. 가장 큰 덩어리 출력
    print(max_cnt)

if __name__ == "__main__":
    n, q = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(2**n)]
    command = list(map(int, input().split()))
    solution(n, q, graph, command)