[21609] 상어 중학교

문제

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

풀이

블록 그룹을 찾을 때 일반 블록이 적어도 하나 이상 포함해야 하기 때문에 일반 블록인 위치를 기준으로 bfs 방식으로 그룹을 찾아주었습니다.

탐색을 하며 중복된 블록 그룹을 찾는 경우를 방지하기 위해서 방문 처리를 해줬습니다. 방문 처리를 하는 과정에서 조심해야 할 부분은 무지개 블록의 방문 처리는 현재 탐색에 한에서만 중복되지 않도록 해주어야 합니다. 현재 탐색하는 블록 그룹 외에도 다른 블록 그룹에서도 포함될 수 있기 때문입니다.

탐색을 종료 할 때마다 찾은 블록 그룹의 정보를 딕셔너리에 기록해줍니다. 키 값으로는 블록의 크기, 무지개 블록의 개수, 행의 번호, 열의 번호 순서대로 기록된 튜플를 넣어줬고, 값으로 탐색된 위치를 저장했습니다.

모든 탐색을 종료 후 블록 그룹의 정보를 저장한 딕셔너리의 키 값을 기준으로 오름차순으로 정렬 후 가장 첫 번째인 블록 그룹을 제거해주면 됩니다.

import sys

N, M = map(int, sys.stdin.readline().split())
moves = ((0, 1), (0, -1), (1, 0), (-1, 0))
board = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
result = 0

def apply_gravity():  # 중력을 작용
    for c in range(N):
        bottom = N-1
        for r in range(N-1, -1, -1):
            if board[r][c] == -2:
                continue
            if board[r][c] == -1:
                bottom = r - 1
                continue
            board[bottom][c] = board[r][c]
            if bottom != r:
                board[r][c] = -2
            bottom -= 1

def rotate(board):  # 격자 90도 회전
    new_board = []
    for c in range(N-1, -1, -1):
        row = []
        for r in range(N):
            row.append(board[r][c])
        new_board.append(row)
    return new_board

def remove_blocks(blocks):  
    for r, c in blocks:
        board[r][c] = -2

while True:
    group = dict()
    visited = [[False] * N for _ in range(N)]
    for r in range(N):
        for c in range(N):
            if visited[r][c] or board[r][c] <= 0:
                continue
            visited[r][c] = True
            stack, passed = [(r, c)], []
            current_color = board[r][c]
            rainbow_color = set()  # 무지개 블록 방문 여부
            while stack:
                cur_r, cur_c = stack.pop()
                passed.append((cur_r, cur_c))
                for move_r, move_c in moves:
                    new_r, new_c = cur_r + move_r, cur_c + move_c
                    if not 0 <= new_r < N or not 0 <= new_c < N:
                        continue
                    if visited[new_r][new_c] or (new_r, new_c) in rainbow_color:
                        continue
                    if board[new_r][new_c] == 0 or current_color == board[new_r][new_c]:
                        visited[new_r][new_c] = True
                        stack.append((new_r, new_c))
                        if board[new_r][new_c] == 0:
                            rainbow_color.add((new_r, new_c))
                            visited[new_r][new_c] = False
            if len(passed) >= 2:
                group[(len(passed), len(rainbow_color), r, c)] = passed
    if len(group) == 0:
        break
    remove_group = group[sorted(group.keys(), reverse=True)[0]]
    remove_blocks(remove_group)
    result += len(remove_group) ** 2
    apply_gravity()
    board = rotate(board)
    apply_gravity()

print(result)