문제링크
문제 설명
2^N * 2^N 크기의 격자 위에서 상어가 파이어스톰을 시전한다.
A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.
파이어스톰의 과정은 다음과 같다.
- 단계 L 결정
- 2^L × 2^L 크기의 부분 격자로 나누기
- 모든 부분 격자를 90도 회전
- 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어들기
Q만큼 파이어스톰을 반복하고, 격자위에 남은 얼음의 총량과 가장 큰 덩어리가 차지하는 칸의 개수를 구하라
문제 풀이
얼음의 양 줄이는 부분이나 bfs로 얼음양, 덩어리 크기 구하는 부분은 비교적 쉽다. 핵심은 격자 나눠서 90도 돌리는 부분인데,,
격자 나누고 90도 회전
각 쿼리에 대해서 격자를 나누고 90도 회전하는 부분은 다음과 같다.
문제에서 주어진 흐름대로 격자 나누기 -> 나눈 격자 zip을 활용해서 90도 회전 -> 다시 board에 넣어주기의 순서로 구현했다.
def rotate_90(parts):
return list(zip(*parts[::-1]))# 1. 2^L * 2^L로 나누기
for i in range(0, 2**N, 2**L):
for j in range(0, 2**N, 2**L):
parts = []
for k in range(i, i+2**L):
parts.append(board[k][j:j+2**L])
# 2. 90도 회전
rotated = rotate_90(parts)
for k in range(2**L):
board[k+i][j:j+2**L] = rotated[k]뭔가 돌아가는 느낌이라 다른 코드들 구글링했는데 수식을 구해서 직접 회전하는것보다 그냥 zip이용하는게 더 직관적으로 느껴져서 따로 수정은 안했다.
얼음의 양 줄이기
주의할 점은, 인접한 칸 중 얼음이 있는 칸이 3개가 안될때 바로 Board를 갱신해주는 것이 아니라 새로운 리스트에 줄일 얼음양을 기록해야 한다.
# 3.얼음의 양 줄이기
decrement = [[0 for _ in range(2**N)] for _ in range(2**N)]
for i in range(2**N):
for j in range(2**N):
if board[i][j] > 0:
count = 0
for d in range(4):
ni, nj = i+dx[d], j+dy[d]
if in_bound(ni, nj):
if board[ni][nj] > 0:
count += 1
if count < 3:
decrement[i][j] = -1
for i in range(2**N):
for j in range(2**N):
board[i][j] += decrement[i][j]총 얼음양과 덩어리 크기 구하기
def bfs(x, y, visited):
queue = deque()
queue.append([x,y])
visited[x][y] = True
count = 1
while queue:
x,y = queue.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if in_bound(nx,ny) and not visited[nx][ny] and board[nx][ny] > 0:
visited[nx][ny] = True
queue.append([nx, ny])
count += 1
return countanswer1 = 0
for i in range(2**N):
answer1 += sum(board[i])
visited = [[False for _ in range(2**N)] for _ in range(2**N)]
answer2 = 0
for i in range(2**N):
for j in range(2**N):
if not visited[i][j] and board[i][j] > 0:
answer2 = max(answer2, bfs(i,j,visited))전체 코드
import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
N, Q = map(int, input().split())
board = []
for _ in range(2**N):
board.append(list(map(int, input().split())))
Levels = list(map(int, input().split()))
def rotate_90(parts):
return list(zip(*parts[::-1]))
def in_bound(x, y):
if x in range(2**N) and y in range(2**N):
return True
return False
def bfs(x, y, visited):
queue = deque()
queue.append([x,y])
visited[x][y] = True
count = 1
while queue:
x,y = queue.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if in_bound(nx,ny) and not visited[nx][ny] and board[nx][ny] > 0:
visited[nx][ny] = True
queue.append([nx, ny])
count += 1
return count
for L in Levels:
# 1. 2^L * 2^L로 나누기
for i in range(0, 2**N, 2**L):
for j in range(0, 2**N, 2**L):
parts = []
for k in range(i, i+2**L):
parts.append(board[k][j:j+2**L])
# 2. 90도 회전
rotated = rotate_90(parts)
for k in range(2**L):
board[k+i][j:j+2**L] = rotated[k]
# 3.얼음의 양 줄이기
decrement = [[0 for _ in range(2**N)] for _ in range(2**N)]
for i in range(2**N):
for j in range(2**N):
if board[i][j] > 0:
count = 0
for d in range(4):
ni, nj = i+dx[d], j+dy[d]
if in_bound(ni, nj):
if board[ni][nj] > 0:
count += 1
if count < 3:
decrement[i][j] = -1
for i in range(2**N):
for j in range(2**N):
board[i][j] += decrement[i][j]
# 남은 얼음합
answer1 = 0
for i in range(2**N):
answer1 += sum(board[i])
visited = [[False for _ in range(2**N)] for _ in range(2**N)]
answer2 = 0
for i in range(2**N):
for j in range(2**N):
if not visited[i][j] and board[i][j] > 0:
answer2 = max(answer2, bfs(i,j,visited))
print(answer1)
print(answer2)소요시간
2시간 반
청소년상어보다 얘가 더 어려운거같은데 ㅠ ㅠ
Hongik CE