[백준 21609번] 상어 중학교 문제 풀이

 

< 문제 >

 

 

< 입출력 >

 

 

< 풀이 >

먼저 문제를 이해해보자.

블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.

→ 블록 그룹의 구성 블록 : 일반 블록 1개이상(단, 색은 모두 같아야 함) / 검은색 블록 X, 무지개 블록 개수 상관 없음

→ 블록의 개수는 2개 이상

→ 블록 그룹 기준 : 검은색 블록이나 일반 블록 중, 가장 위에 있는 블록, 여러개면 그 중 가장 왼쪽에 있는 블록

 

오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.
1. 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된
무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B^2점을 획득한다.
3. 격자에 중력이 작용한다.
4. 격자가 90도 반시계 방향으로 회전한다.
5. 다시 격자에 중력이 작용한다.

→ 크기가 가장 큰 블록, 여러 개라면 무지개 블록의 수가 가장 많은 블록 그룹, 여러 개라면 가장 아래에 있는 것 , 여러 개라면 가장 오른쪽에 있는 것

→ 찾을 블록 그룹의 모든 블록 제거하고, 블록 개수의 제곱만큼 점수 획득

→ 중력 → 90도 반시계 → 중력

 

 

구현하기 위해서 중력 함수, 반시계 회전 함수, 가장 큰 블록을 구하는 함수를 짜야한다.

 

 

 

< 반시계 회전 함수 로직 >

• 규칙 찾기 ( N = 5 일때 )

기존      →     신규 

(0, 4)     →     (0, 0)

(1, 4)     →     (0, 1)

(2, 4)     →     (0, 2)

(0, 3)     →     (1, 0)

(3, 2)    →      (2, 3)

  

새로운 x  ← 기존 N - 1 - x 

새로운 y  ← 기존 x

 

def rotate(arr):       # 반시계 회전 함수
	global block
    tmp = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            tmp[i][j] = tmp[j][N - i -1]
    block = tmp

 

 

 

 

< 중력 함수 로직 >

격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.

def gravity(arr):      # 중력 함수
    for i in range(n-2, -1, -1):   # 맨 마지막 행 바로 위의 행부터 검사 
    	for j in range(n):
        	if block[i][j] != -1:
            	pointer = i
                
                while pointer + 1 <n and block[pointer + 1][j] == -2:
                	block[pointer + 1][j] = block[pointer][j]
                    block[pointer][j] =-2
                    pointer += 1

 

 

 

< 가장 큰 블록 찾는 로직 >

def find_biggest(i, j, block_num):   # 행열의 위치와 블록 그룹의 개수
	q = deque()
    q.append((i, j))
    
    normals = [[i, j]]   # 일반 블록 위치 저장
    rainbow = []
    
    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 block[nx][ny] == 0 and not visited[nx][ny]:  # 방문하지 않은 무지개 블록이면 
                	q.append((nx, ny))
                    rainbows.append([nx, ny])
                    visited[nx][ny] = 1
                    
                elif block[nx][ny] == block_num and not visited[nx][ny]:  # 방문하지 않은 일반 블록이면
                	q.append((nx, ny))
                    normals.append([nx, ny])
                    visited[nx][ny] = 1
                    
	for x, y in rainbows:    # 무지개 블록은 다른 블록 그룹을 만들 때 중복될 수 있으므로 visited = 0 처리
    	visited[x][y] = 0 
        
    return [len(normals+ rainbows), len(rainbows), normal + rainbows]

 

 

< 블록 그룹 삭제 로직 >

def remove_block(group):
	global score
    score += group[0] ** 2
    
    for x, y in group[2]:
    	block[x][y] = -2

 

 

 

< 전체 코드 >

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

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def find_biggest(i, j, block_num):

    q = deque()
    q.append((i, j))

    normals = [[i, j]]  #일반 블록 위치 저장
    rainbows = []

    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 block[nx][ny] ==0 and not visited[nx][ny]:
                    q.append((nx, ny))
                    rainbows.append([nx, ny])
                    visited[nx][ny] = 1

                elif block[nx][ny] == block_num and not visited[nx][ny]:
                    q.append((nx, ny))
                    normals.append([nx, ny])
                    visited[nx][ny] = 1

    for x, y in rainbows:
        visited[x][y] = 0

    return [len(normals + rainbows), len(rainbows), normals + rainbows]

def gravity():
    for i in range(n - 2, -1, -1):
        for j in range(n):
            if block[i][j] != -1:
                pointer = i

                while pointer + 1 < n and block[pointer + 1][j] == -2:
                    block[pointer + 1][j] = block[pointer][j]
                    block[pointer][j] = -2
                    pointer += 1


def rotate_block():
    global block
    tmp = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            tmp[n-j-1][i] = block[i][j]
    block = tmp


def remove_block(group):
    global score
    score += group[0] ** 2

    for x, y in group[2]:
        block[x][y] = -2


n, m = map(int, input().rstrip('\n').split())
block = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
score = 0
while True:
    visited = [[0] * n for _ in range(n)]
    groups = []

    for i in range(n):
        for j in range(n):
            if block[i][j] >= 1 and not visited[i][j]:
                visited[i][j] = 1
                group = find_biggest(i, j, block[i][j])

                if group[0] >= 2:
                    groups.append(group)

    groups.sort(reverse=True)
    if not groups:
        break

    remove_block(groups[0])
    gravity()
    rotate_block()
    gravity()

print(score)