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

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

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

설명

파이어스톰을 크기가 2^n x 2^n 인 격자로 나누어진 얼음판에서 연습하려한다. 위치 (r,c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r,c)에 있는 얼음의 양을 의미. A[r][c]가 0인 경우 얼음이 없는 것을 뜻한다. 파이어스톰을 시전할 때마다 단계 L을 결정해야 한다. 

• 먼저, 격자를 2^L x 2^L 크기의 부분 격자로 나눈다.
• 그 후, 모든 부분 격자를 시계 방향으로 90도 회전 시킨다. 
• 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해 있지 않은 칸은 얼음의 양이 1 줄어든다. 
• (r,c)와 인접한 칸은 (r-1,c), (r+1,c), (r,c-1), (r, c+1)이다. 

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

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

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

핵심 아이디어

삼성이 좋아하는 배열 회전 문제이다. 이쯤되면 시계방향과 반시계 방향 정도는 외워두는 것이 편하다. 삼성 문제는 문제를 정확하게 이해하는 것이 중요!

• 구현, 시뮬레이션, BFS 문제이다. 먼저, 격자를 나눠서 회전시키는 함수, 그리고 얼음의 양을 줄어들게 하는 함수, 얼음 덩어리를 세는 함수 3가지로 구현하기. 단계를 돌면서 divide와 reduce함수를 실행시키고, 마지막에 얼음 덩어리의 최개 개수를 구하면서 bfs함수를 써주면 된다. 
• divide 함수: 격자의 길이는 2^L이다. 행, 열에 대해서 격자의 길이만큼 증가시키면서 임시 배열을 만들어주고, 그 임시배열을 회전시킨 후 원배열에 할당해주기. 
• reduce 함수: 모든 좌표에 대해서 상하좌우를 탐색하며 인접한 칸중에 얼음이 존재하는 칸이 몇개인지 세주고, 그 수가 2개 이하라면 원배열에서 1을 빼주자. 하지만 원배열에 바로 적용을 하면 동시에 얼음의 양이 줄어드는 것이 아닌 순차적으로 줄어들게 되는 것이므로 임시배열에 할당을 해놓고, 나중에 적용하자. 또한 안 녹는 얼음이 존재할 수 있기 때문에 임시 배열에 저장.
• bfs 함수: 얼음 덩어리를 세기 위하여 큐에 좌표를 저장하고, 상 하 좌 우로 탐색하면서 얼음이 있으면 큐에 또 저장하면서 탐색을 진행하게 된다. 단, 방문집합을 하나 생성해서 한번 방문한 곳은 다시 방문하지 않도록 해야한다. 

★회전 하기

출처: https://youbin-shin.github.io/

위 방식을 이용해서 회전 시키기 적용

• temp[x1+y2][y1 + cnt - x2 - 1] = graph[x1+x2][y1+y2]

코드구현

# 코드 1

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

# 총 q번 시전
n, q = map(int, input().split())
N = 2**n
# 얼음 맵 정보 입력받기
graph = [list(map(int, input().split())) for _ in range(N)]
# q번의 L입력받기
q_list = map(int, input().split())
# 방향 정의 입력받기
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# 얼음 덩어리 카운트 할 때 방문 정보 확인을 위한 리스트
visited = [[False] * N for _ in range(N)]

# 격자 나누고, 90도 회전하는 함수
def divide_and_rotate(graph, L):
	# 임시 배열 만들기
	# rotate
	temp = [[0] * N for _ in range(N)]
	cnt = 2**L # 격자 사이즈
	for x1 in range(0, N, cnt):
		for y1 in range(0, N, cnt):
			for x2 in range(cnt):
				for y2 in range(cnt):
					temp[x1+y2][y1+ cnt - x2 - 1] = graph[x1 + x2][y1+y2]
	return temp
# 얼음의 양을 줄이는 함수 정의
def reduce(graph):
	# 임시 배열 만들기
	temp = [[0] * N for _ in range(N)]
	for x in range(N):
		for y in range(N):
			cnt = 0 # 인접한 칸 중 얼음이 있는 개수
			for d in range(4):
				nx = x + dx[d]
				ny = y + dy[d]
				# 인접하고 얼음이 있으면
				if (0<=nx<N) and (0<=ny<N) and graph[nx][ny] > 0:
					cnt += 1
			# 카운트 2 이하면
			if cnt < 3 and graph[x][y] > 0:
				temp[x][y] = 1 # 얼음 1 주이기 임시 배열에 저장
	# 한번에 원배열에 저장
	for x in range(N):
		for y in range(N):
			if temp[x][y] == 1 and graph[x][y] > 0:
				graph[x][y] -= 1
	return graph
# 얼음 덩어리가 차지하는 칸의 수 세기
def bfs(x,y):
	q = deque()
	q.append((x,y))
	visited[x][y] = True
	# 현재 칸은 포함해서 시작
	cnt = 1
	while q:
		x,y = q.popleft()
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if (0<=nx<N) and (0<=ny<N):
				if not visited[nx][ny] and graph[nx][ny] > 0:
					visited[nx][ny] = True
                    # 연결 됐기 때문에 칸 수 하나 늘어남
					cnt += 1
					q.append((nx,ny))
	return cnt # 덩어리가 차지하는 칸 출력
# 단계 실행
for L in q_list:
	graph = divide_and_rotate(graph, L)
	graph = reduce(graph)
ans = 0
# 남아 있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
max_ans = 0
for i in range(N):
	for j in range(N):
		if graph[i][j] > 0:
			ans += graph[i][j]
			# 얼음 덩어리의 칸의 수 비교
			max_ans = max(max_ans, bfs(i,j))
print(ans)
print(max_ans)

# 초기 셋팅

# queue 구현을 위해 deque 활용
from collections import deque

# 파이어스톰을 총 q번 시전
n, q = map(int, input().split())
# 얼음 배열 입력받기
graph = [list(map(int, input().split())) for _ in range(2**n)]
# 시전한 단계 입력받기
q_list = map(int, input().split())
# 얼음을 카운트 할 때 방문정보 확인을 위한 배열
visited = set()
# 상 하 좌 우 
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# 배열의 길이
length = 2**n

# 격자 나누고 90도 회전시키는 함수 정의

def divide(graph, L):
	cnt = 2**L # 격자의 길이
    for i in range(0, length, cnt):
    	for j in range(0, length, cnt):
        	# 임시 배열 만들기
            temp = []
            for k in range(cnt):
            	temp.append(graph[i+k][j:j+cnt]) # 임시 배열 만들기
            temp = list(zip(*temp[::-1])) # 오른쪽으로 90도 회전하기
            for k in range(cnt):
            	graph[i+k][j:j+cnt] = temp[k] # 원래 배열에 반영
    return graph

# 얼음의 양을 줄이는 함수 정의

def reduce(graph):
	# 임시 배열 만들기
    temp = [[0] * length for _ in range(length)]
    for x in range(length):
    	for y in range(length):
        	cnt = 0 # 인접한 칸 중 얼음이 있는 개수
            for d in range(4):
            	nx = x + dx[d]
                ny = y + dy[d]
                if (0<=nx<length) and (0<=ny<length):
                	if graph[nx][ny] > 0: # 인접하고 얼음이 있으면
                    	cnt += 1
        # 카운트 2 이하면
        if cnt <= 2 and graph[x][y] > 0:
        	temp[x][y] -= 1 # 얼음 1 줄이기 임시 배열에 저장
	#  한번에 원배열에 저장
    for x in range(length):
    	for y in range(length):
        	graph[x][y] += temp[x][y]
    return graph

# 얼음 덩어리 개수 세기

def bfs(x,y):
	q = deque()
    q.append((x,y))
    visited.add((x,y))
    # 얼음 덩어리 개수
    cnt = 1
    while q:
    	x, y = q.popleft()
        for i in range(4):
        	nx = x + dx[i]
            ny = y + dy[i]
            if (0<=nx<length) and (0<=ny<length):
            	# 만약 한번도 방문하지 않았고 얼음이 있다면
                	if (nx,ny) not in visited and graph[nx][ny] > 0:
                    	visited.add((nx,ny))
                        cnt += 1 # 얼음 덩어리 개수 증가
                        q.append((nx,ny))
	return cnt

# 단계 실행

for L in q_list:
	divide(graph, L)
    reduce(graph)
# 얼음 총 합
ans = 0
# 남아 있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
max_ans = 0
for i in range(length):
	for j in range(length):
    	if graph[i][j] > 0:
        	ans += graph[i][j]
            max_ans = max(max_ans, bfs(i,j))
print(ans)
print(max_ans)

# 코드 2

import sys
input = sys.stdin.readline

# queue 구현을 위해 deque 사용
from collections import deque

# 파이어스톰을 총 q번 시전하려한다.
n, q = map(int, input().split())
# 얼음 배열 입력받기
graph = [list(map(int, input().split())) for _ in range(2**n)]
level = list(map(int, input().split())) # L단계
# 얼음덩어리 방문 배열
visited = set() # 중복제거, 순서 고려x
# 상 하 좌 우
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# 배열의 길이
length = 2**n

# 격자 나눠숴 90도 회전 시키기
def divide(graph, L):
	cnt = 2**L # 격자의 길이
	for i in range(0, length, cnt):
		for j in range(0, length, cnt):
			temp = [] # 임시 배열
			for k in range(cnt): # 격자의 길이만큼
				temp.append(graph[i+k][j:j+cnt]) # 임시 배열 만들기
			temp=list(zip(*temp[::-1])) # 오른쪽 90도회전
			for k in range(cnt):
				graph[i+k][j:j+cnt]=temp[k] # 원래 배열에 반영
	return graph

# 얼음양 줄어들기
def reduce(graph):
	# 임시 배열만들기
	temp = [[0] * length for _ in range(length)]
	for x in range(length):
		for y in range(length):
			cnt = 0 # 인접한 칸중 얼음이 있는 개수
			for d in range(4):
				nx = x + dx[d]
				ny = y + dy[d]
				if (0<=nx<length) and (0<=ny<length):
					# 인접하고 얼음이 있으면
					if graph[nx][ny] > 0:
						cnt += 1
			# 카운트 2 이하면
			if cnt <= 2 and graph[x][y] > 0:
				temp[x][y] -= 1 # 얼음 1 줄이기 임시 배열에 반영
	for x in range(length):
		for y in range(length):
			# 원배열에 한번에 적용
			graph[x][y] += temp[x][y]
	return graph

# 얼음 덩어리 개수 세기
def bfs(x,y):
	q = deque()
	q.append((x,y)) # 큐에 저장
	visited.add((x,y)) # 방문
	cnt = 1 # 덩어리 개수
	while q:
		x,y = q.popleft()
		for i in range(4): # 네 방향에 대하여
			nx = x + dx[i]
			ny = y + dy[i]
			if (0<=nx<length) and (0<=ny<length):
				# 방문하지 않았고 0이 아니면
				if (nx,ny) not in visited and graph[nx][ny] != 0:
					q.append((nx,ny))
					visited.add((nx,ny))
					cnt += 1 # 덩어리 개수 증가
	return cnt

# 단계 실행
for L in level:
	divide(graph, L)
	reduce(graph)
ans = 0 # 남아 있는 얼음의 합
max_ans = 0 # 남아 있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수
for i in range(length):
	for j in range(length):
		if graph[i][j] > 0:
			ans += graph[i][j] # 누적합
			max_ans = max(max_ans, bfs(i,j)) # 최대 덩어리 값
print(ans)
print(max_ans)