초이의 끄적끄적

# 20058 마법사 상어와 파이어스톰 (골드4)

유형 : 시뮬레이션 문제, DFS

문제

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

mport sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
dx = [1,0,-1,0]
dy = [0,1,0,-1]

n, q = map(int, input().split())
n = 2 ** n
ice = [list(map(int, input().split())) for _ in range(n)]

# 회전 확인해보기
# count = 1
# ice = [[0]*(n) for i in range(n)]
# for i in range(n):
#     for j in range(n):
#         ice[i][j] = count
#         count+=1
# print(ice)

for L in list(map(int, input().split())):
    # 회전
    k = 2 ** L
    for x in range(0, n, k):
        for y in range(0, n, k):
            tmp = []
            for i in range(x, x + k):
                tmp.append(ice[i][y:y + k])
            # print(tmp)
            # tmp = [ice[i][y:y + k] for i in range(x, x + k)]
            for i in range(k):
                for j in range(k):
                    ice[x + j][y + k - 1 - i] = tmp[i][j]
    # print(ice)

    # 인접 얼음 카운팅
    cnt = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            for d in range(4):
                nx = i+ dx[d]
                ny = j+ dy[d]
                if 0<= nx < n and 0<= ny < n and ice[nx][ny] > 0:
                    cnt[i][j] +=1

    # 얼음 제거
    for x in range(n):
        for y in range(n):
            if ice[x][y] >0 and cnt[x][y] <3:
                ice[x][y] -= 1

# print(ice)
print(sum(sum(i) for i in ice))

# (x,y)가 속한 덩어리의 크기
def dfs(x, y):
    global ans
    ret = 1
    ice[x][y] = 0
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < n and 0 <= ny < n and ice[nx][ny]:
            ret += dfs(nx, ny)
    ans = max(ans,ret)
    return ret

# 제일 큰 덩어리
ans = 0
for x in range(n):
    for y in range(n):
        if ice[x][y] > 0:
            dfs(x, y)

print(ans)

참고