[백준] 20058번 : 마법사 상어와 파이어스톰

[백준] 20058번 : 마법사 상어와 파이어스톰

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

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

📄 문제개요

• 2^Nx2^N인 격자로 나누어진 얼음판이 존재한다.
• 해당 얼음판에서 2^Lx2^L크기의 부분격자로 나눈뒤 모든 부분 격자를 시계 방향으로 90도 회전시킨다.
• 회전시킨후 각자의 위치에서 주변의 얼음이 3개 이하인경우 그자리에 있는 얼음을 녹인다.
• L 만큼 부분격자를 나누라는 명령이 Q번 주어진다.
• 출력으로는 첫재쭐에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다.

🤔 문제분석

• LxL의 부분격자로 나눈다. 분할정복 LxL을의 배열을 방문 할 수 있게 만든다.
• 부분격자에 도달하였으면 시계방향으로 90도를 회전하는 방법을 구현한다.
• 2중 for문을 돌면서 얼음을 녹인다.
• 남아있는 얼음의 합을 구한다. 둘째줄에는 가장 큰 덩어리가 차지하는 칸의 개수를 너비우선탐색으로 계산한다.

📝 의사코드

1. 재귀호출하여 LxL을 부분격자로 나눈다.
   1. 8x8에서 2x2의 부분격자의 재귀 호출 과정
      1. 8x8에서 4개의 사분면 4x4로 나눈뒤 재귀호출한다.
      2. 4x4에서 4개의 사분면 2x2로 나눈뒤 재귀호출한다.
      3. 2x2에 도달 하였음.
2. 재귀호출에 도달했다면, 해당위치에서 90도를 회전시키는 로직을 호출한다.
3. 2중 for문을 돌면서 자기자신 4곳중 얼음이 3이하 인경우는 얼음의 양을 1 줄인다.
4. 주어진 명령어의 수 Q를 1번 ~ 3번을 반복한다.
5. 1~4번이 끝났다면, 얼음의 합을구한다. 가장 큰 덩어리가 차지하는 칸의 개수는 너비우선탐색으로 개수를 구한다.
   1. 너비우선탐색으로 개수를 구할때 2중 for문을 돌면서 얼음을 만나면 자기자신의 인접한 얼음을 방문해가면서 그룹개수를 새어나간다. ( 방문처리 필수 )
   2. 그룹의 개수가 가장 많은 개수를 출력하면 된다.

💻 코드

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

move = [(0,1), (1,0),(-1,0), (0,-1)]

N, Q = map(int, input().split())
ice = []
for _ in range(2**N):
    ice.append(list(map(int, input().split())))

cmd = list(map(int, input().split()))

def find_max_group():
    visited = [[False for _ in range(2**N)] for _ in range(2**N)]
    ans = 0
    for i in range(2**N):
        for j in range(2**N):
            cnt = 0
            if ice[i][j] >0 and not visited[i][j]:
                visited[i][j] = True
                queue = deque()
                queue.append((i, j))
                cnt = 1
                while queue:
                    y, x = queue.popleft()
                    for dy, dx in move:
                        ny , nx = dy + y, dx + x
                        if 2**N > ny >=0 and 2**N > nx >=0 and not visited[ny][nx] and ice[ny][nx] > 0:
                            cnt += 1
                            visited[ny][nx] = True
                            queue.append((ny, nx))
                            
            ans = max(ans, cnt)
                            
    return ans
    

def melt():
    temp = [[0 for _ in range(2**N)] for _ in range(2**N)]
    for i in range(2**N):
        for j in range(2**N):
            cnt = 4
            for dy, dx in move:
                ny, nx = dy+i, dx + j
                if 2**N > ny >=0 and 2**N > nx >=0 and ice[ny][nx] > 0:
                    cnt -= 1
            if cnt >= 2:
                temp[i][j] = 1
    
    for i in range(2**N):
        for j in range(2**N):
            if ice[i][j] > 0:
                ice[i][j] -= temp[i][j]
            
            

def rotate(start, end, size):
    temp = [[0 for _ in range(size)] for _ in range(size)]
    for i in range(size):
        for j in range(size):
            temp[j][size-1-i] = ice[i+start][j+end]
            
    for i in range(size):
        for j in range(size):
            ice[i+start][j+end] = temp[i][j]
    

def dfs(start, end, size):
    if size == 2**L: # 시계방향으로 회전시킨다.
        rotate(start, end, size)
        return
    
    mid = size // 2
    dfs(start, end, size//2) # 왼쪽 위
    dfs(start + mid, end, size//2) # 왼쪽 아래
    dfs(start, end + mid, size//2) # 오른쪽 위
    dfs(start + mid, end + mid, size//2) # 오른쪽 아래

for i in range(Q):
    L = cmd[i]
    dfs(0, 0, 2**N)
    melt()
    
ans = 0
for ic in ice:
    #print(ic)
    ans += sum(ic)
    
print(ans)
print(find_max_group())

🎯 피드백 및 개선사항

<aside> 💡 배열을 회전하는 로직이 중요하다.

</aside>

123

4	5	6
7	8	9

회전 전

741

8	5	2
9	6	3

회전 후

행렬은 다음과 같이 90도 회전했을때 나타낼 수 있다.

행의 순서는 열을 나열하는 순서와 바뀌지 않는다.

나열하는 순서가 바뀐다.

1. 1번째 행이 3번째 열에 배치
2. 2번째 행이 2번째 열에 배치
3. 3번째 행이 1번째 열에 배치

점화식은 다음과 같이 표현할 수 있다.

new_table[i][j] = table[j][N-i-1]

for i in range(N):
	for j in range(N):
		new_table[i][j] = table[j][N-i-1]