[ 21609 ] [ 구현 ] 상어 중학교

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

21609번: 상어 중학교

 

---

풀이 과정

---

1. BFS 알고리즘을 사용하여 크기가 가장 큰 블록 그룹을 찾는다.
   1. 이 때, 크기가 같은 경우 무지개 블록의 수를 비교하여서 갱신시킨다.
   2. 기준 블록을 왼쪽 위에서 오른쪽 아래 순서로 골라서 블록 그룹을 찾으므로 현재 고른 블록이 기준 블록의 행이 가장 크고 열이 가장 큰 것이다. 따라서 크기가 같고 무지개 블록의 수도 같은 경우는 갱신시켜 주어야 한다.
2. (1)에서 구한 블록 그룹을 모두 제거한다. 이 때 점수도 같이 구해준다.
   • 제거 표시는 -2로 표시하고, 점수는 블록 그룹 내 블록의 수 제곱을 해준다.
3. 중력 기능을 구현한다.
   • 가장 아래 행에서부터 시작해서 하나하나의 요소들을 아래에 -2가 나타나지 않을때까지 당겨준다.
4. 회전 기능을 구현한다.
   • matrix[i][j] = matrix[j][len(matrix[0])-1-i]
5. 구현 순서에 맞추어서 전체 기능을 조합한다. 이 때, 최대 블록 그룹을 구했을 때, 그룹이 없거나 그룹 내 블록의 수가 1개인 경우에 게임을 종료시킨다.

---

소스 코드

---

 

import sys
from collections import deque
import copy


input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

def bfs(matrix, startX, startY):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    queue = deque([[startX, startY]])
    block_color = matrix[startX][startY]
    matrix[startX][startY] = -1
    block_count = 1
    rainbow = []
    block = [[startX, startY]]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < N and 0 <= ny and ny < N:
                if matrix[nx][ny] == block_color or matrix[nx][ny] == 0:
                    queue.append([nx, ny])
                    block.append([nx, ny])
                    block_count += 1
                    if matrix[nx][ny] == 0:
                        rainbow.append([nx, ny])
                    matrix[nx][ny] = -1

    for nx, ny in rainbow:
        matrix[nx][ny] = 0

    return block, block_count, len(rainbow)

def find_max_block(target):
    matrix = copy.deepcopy(target)
    max_block, max_block_count, max_rainbow = None, 0, 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] > 0:
                block, block_count, rb_len = bfs(matrix, i, j)
                if max_block_count < block_count:
                    max_block, max_block_count, max_rainbow = block, block_count, rb_len
                elif max_block_count == block_count:
                    if max_rainbow <= rb_len:
                        max_block, max_block_count, max_rainbow = block, block_count, rb_len

    return max_block

def destroy(matrix, block):
    for x, y in block:
        matrix[x][y] = -2

def gravity(matrix):
    for i in range(len(matrix)-2, -1, -1):
        for j in range(len(matrix[0])):
            index = i
            if matrix[i][j] == -1:
                continue
            while index+1 != N and matrix[index+1][j] == -2:
                matrix[index+1][j] = matrix[index][j]
                matrix[index][j] = -2
                index += 1

def rotate(matrix):
    new_matrix = copy.deepcopy(matrix)
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            new_matrix[i][j] = matrix[j][len(matrix)-1-i]

    return new_matrix
            

score = 0

while True:
    block = find_max_block(matrix)
    if block == None:
        break
    if len(block) <= 1:
        break
    score += (len(block) ** 2)
    destroy(matrix, block)
    gravity(matrix)
    matrix = rotate(matrix)
    gravity(matrix)

print(score)