[알고리즘] 마법사 상어와 파이어스톰

포인트

• 음.. 시간을 재면서 풀었는데, 가끔이 신이 들린 것처럼 생각하도 않고 코딩을 한 것 같습니다. 이렇게 중간마다 희망을 주면 빠르게 포기를 못해요 ㅠㅠ
• 문제는 정말 심플합니다. 
  
  
• L을 준다. 90도 시계 방향으로 회전한다. 
• 근접 얼음을 계산해 준 후 반영
• 최종 얼음의 개수와 가장 큰 덩어리를 출력

설계를 하는 것도 중요하지만, "중간마다 만든 기능의 허점이 있는지?"를 아는 것도 매우 중요한 것 같습니다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

from collections import deque
from copy import deepcopy
import sys

sys.stdin = open('input.txt')

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

commands = list(map(int, input().split()))
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def rotate_data_with_l():
	"""
	l 만큼의 범위로 회전 구역을 90도로 회전 합니다.
	tail to head
	"""
	global data
	copy = [[0] * nn for _ in range(nn)]
	for row in range(0, nn, l):
		for col in range(0, nn, l):
			# 시작 점 정하기
			temp1 = []
			for i in range(row, row + l):
				temp = []
				for j in range(col, col + l):
					temp.append(data[i][j])
				temp1.append(temp)
			rotate = [list(line) for line in zip(*temp1[::-1])]
			
			for i in range(l):
				for j in range(l):
					copy[row + i][col + j] = rotate[i][j]
	data = deepcopy(copy)


def count_lower_3() -> None:
	"""
	근접 얼음이 3개 미만인 구역을 저장합니다. (0인 부분도 포함하여)
	저장하는 이유는 중복된 칸을 세지 않기 위해
	"""
	for row in range(nn):
		for col in range(nn):
			cnt = 0
			for i in range(4):
				nx = row + dx[i]
				ny = col + dy[i]
				if not (0 <= nx < nn and 0 <= ny < nn) or data[nx][ny] == 0:
					continue
				cnt += 1
			if cnt < 3:
				vc.append((row, col))


def bfs(a: int, b: int) -> int:
	"""
	시작점을 기준으로 일반적인 bfs 를 진행하여 제일 큰 땅의 크기를 세어줍니다.
	:param a:
	:param b:
	:return:
	"""
	q = deque()
	q.append([a, b])
	visited[a][b] = 1
	cnt = 1
	while q:
		x, y = q.popleft()
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			
			if not (0 <= nx < nn and 0 <= ny < nn):
				continue
			if visited[nx][ny] == 0 and data[nx][ny] != 0:
				q.append([nx, ny])
				visited[nx][ny] = 1
				cnt += 1
	return cnt


for command in commands:
	# 커맨드를 실행하여 줍니다. 
	l = 2 ** command
	rotate_data_with_l()
	
	vc = []
	count_lower_3()
	
	for row, col in vc:
		if data[row][col] == 0:
			continue
		data[row][col] -= 1
	vc.clear()

visited = [[0] * nn for _ in range(nn)]
answer = 0

for row in range(nn):
	for col in range(nn):
		if visited[row][col] == 1 or data[row][col] == 0:
			continue
		result = bfs(row, col)
		answer = max(answer, result)

result = 0
for row in data:
	result += sum(row)

print(result)
print(answer)