[BOJ][🟡3][백준#20058] 마법사 상어와 파이어스톰

문제 출처

BAEKJOON Online Judge #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)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법을 시전하기 전 L = 1 L = 2

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

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

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

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다. 마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, …, LQ가 순서대로 주어진다.

출력

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

제한

2 ≤ N ≤ 6 1 ≤ Q ≤ 1,000 0 ≤ A[r][c] ≤ 100 0 ≤ Li ≤ N

예제

예제 1

입력

3 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1

출력

284
64

예제 2

입력

3 2
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2

출력

280
64

예제 3

입력

3 5
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 0 3 2

출력

268
64

예제 4

입력

3 10
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 0 3 2 1 2 3 2 3

출력

248
62

예제 5

입력

3 10
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 1 2 3 1 2 3 1

출력

246
60

예제 6

입력

3 10
1 0 3 4 5 6 7 0
8 0 6 5 4 3 2 1
1 2 0 4 5 6 7 0
8 7 6 5 4 3 2 1
1 2 3 4 0 6 7 0
8 7 0 5 4 3 2 1
1 2 3 4 5 6 7 0
0 7 0 5 4 3 2 1
1 2 3 1 2 3 1 2 3 1

출력

37
9

My Sol

import sys
input = sys.stdin.readline

def main():
    def rotate():
        for i in range(0, TL, SL):
            for j in range(0, TL, SL):
                rotate_square(i, j)

    def rotate_square(si, sj):
        square_new = [[0]*SL for _ in range(SL)]
        for i in range(SL):
            for j in range(SL):
                square_new[i][j] = mat[si+SL-1-j][sj+i]

        for i in range(SL):
            for j in range(SL):
                mat[si+i][sj+j] = square_new[i][j]

    def remove_ice():
        del_arr = []
        for i in range(TL):
            for j in range(TL):
                if not mat[i][j]: continue
                ice_cnt = 0
                for di, dj in ((-1,0),(1,0),(0,1),(0,-1)):
                    si, sj = i+di, j+dj
                    if not (0<=si<TL and 0<=sj<TL): continue
                    if not mat[si][sj]: continue
                    ice_cnt += 1

                if ice_cnt < 3:
                    del_arr.append((i, j))

        for ki, kj in del_arr:
            mat[ki][kj] -= 1

    # 전체 얼음 양 계산
    def calc_sum_ice():
        sum_ice = 0
        for i in range(TL):
            for j in range(TL):
                sum_ice += mat[i][j]
        return sum_ice

    # 최대 얼음 크기 계산
    def calc_max_ice():
        def calc_ice(i, j):
            Q = set()
            Q.add((i, j))
            cur_ice = 0
            while Q:
                i, j = Q.pop()
                if not (0<=i<TL and 0<=j<TL): continue
                if visit[i][j] or not mat[i][j]: continue
                visit[i][j] = 1
                cur_ice += 1
                for di, dj in ((-1,0),(1,0),(0,1),(0,-1)):
                    Q.add((i+di, j+dj))
            return cur_ice

        visit = [[0]*TL for _ in range(TL)]
        max_ice = 0
        for i in range(TL):
            for j in range(TL):
                if not mat[i][j]: continue
                cur_ice = calc_ice(i, j)
                if max_ice < cur_ice:
                    max_ice = cur_ice
        return max_ice

    N, Q = map(int, input().split())
    TL = 2**N
    mat = [list(map(int, input().split())) for _ in range(TL)]
    qs = list(map(int, input().split()))
    for q in qs:
        SL = 2**q
        if q: rotate()
        remove_ice()

    print(calc_sum_ice())
    print(calc_max_ice())

main()

단순 구현문제였다. 6달 전에 해결에 실패했는데, 다시 보니 input의 크기가 최대 1000x1000으로 크기가 커서 sys.stdin.readline의 입력 처리만 해주면 되는 문제였다.

1. 위에서 했듯, 입력 크기가 크므로 readline을 사용해 입력을 처리한다. 2의 N제곱만큼 전체 2차원 배열이 주어지므로 그 전체 길이를 TL로, 2차원 배열을 mat으로 명명해 처리했다. 각 q들의 리스트를 qs로 명명해 리스트로 받았다.
2. q는 2의 q제곱을 단위로 90도 시계방향 회전하므로 이 각 q마다 모든 루틴을 진행하면 되겠다. 이때 2의 q제곱을 SL로 명명했다.
3. q가 0이면 회전 단위는 1이므로 회전 전후가 같다. 때문에 q가 1 이상일 때만 회전시키는 rotate 함수를 실행했다.
4. rotate 함수는 mat의 각 SL 단위 격자마다 rotate_square 함수를 실행한다. 이 함수는 시작점을 기준으로 기존 mat의 해당 격자를 90도 회전시켜 mat에 다시 적용시켜준다.
5. 이렇게 모든 단위격자마다 rotate_square을 실행하는 rotate 함수를 모두 마치면, 주변의 얼음을 확인해 녹여주는 함수를 실행한다. 이 함수를 remove_ice라고 명명했다.
6. remove_ice 함수에서 모든 mat의 얼음이 있는 포인트의 상하좌우를 확인해 값이 있는 상하좌우 포인트가 3이하이면 얼음을 녹여주는 del_arr에 추가한다. 이때 바로 해당 포인트의 값을 깎지 않는 이유는 해당 포인트가 1에서 0으로, 완전히 물이 되었을 때 다른 격자의 주변 체크에 영향을 주기 때문이다. 때문에 현 시점을 완전히 고정하고, 현 시점에서 얼음을 녹여주는 리스트를 모두 모은 뒤, 한 번에 1씩 깎아주게 된다.
7. 위의 2부터 6의 루틴을 모든 q에 대하여 진행해주면, 남은 mat으로부터 전체 얼음 양과 최대 얼음 크기를 구해주면 되겠다. 이를 각각 calc_sum_ice, calc_max_ice 함수로 구현했다.
8. calc_sum_ice는 mat을 모두 단순순회하며 값을 더해 반환하는 함수이다.
9. calc_max_ice는 방문하지 않은 얼음 칸에 도달하면 연결된 모든 얼음들을 확인하며 전체 얼음덩어리의 크기를 보는 calc_ice BFS함수를 매번 실행하는 함수이다. 이때 calc_ice 함수로 각 덩어리들의 크기를 파악하면, 이 값들을 누적 최댓값과 대조하여 전체 얼음덩어리의 최대 크기를 파악할 수 있게 된다. 이를 찾아 반환한다.
10. 이를 출력해준다.

결과

맞았습니다!!