문제 링크

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

문제 설명

• 블록 그룹 조건
  • 한 색깔의 일반 블록, 무지개 블록으로만 이루어짐
  • 블록 2개 이상
  • 일반 블록 한 개 이상
  • 기준 블록
    • 무지개 블록이 아닌 블록 중 가장 왼쪽 위
• 순서
  • 가장 큰 블록 그룹 찾기
    • 가장 크면서, 무지개 블록이 많고, 기준 블록이 가장 오른쪽 아래
  • 제거
  • 중력 작용
  • 회전
  • 중력 작용

코드

import sys
from collections import deque

def solution():
    score = 0
    read = sys.stdin.readline
    n, m = map(int, read().split())
    board = [list(map(int, read().split())) for _ in range(n)]

    while True:

        # 최대 블록 그룹 찾기
        max_size = 0
        max_rainbow = 0
        visited = [[0]*n for _ in range(n)]
        max_positions = []
        my, mx = -1, -1
        for y in range(n):
            for x in range(n):
                if board[y][x] > 0 and not visited[y][x]:
                    positions, rainbow = bfs(y, x, n, visited, board, board[y][x])
                    size = len(positions)
                    if max_size < size:
                        max_size = size
                        max_rainbow = rainbow
                        max_positions = positions
                        my, mx = y, x
                    elif max_size == size:
                        if max_rainbow < rainbow:
                            max_rainbow = rainbow
                            max_positions = positions
                            my, mx = y, x
                        elif max_rainbow == rainbow:
                            if my < y:
                                max_positions = positions
                                my, mx = y, x
                            elif my == y:
                                if mx < x:
                                    max_positions = positions
                                    my, mx = y, x

        # 블록 없으면 종료
        if max_size < 2 or max_rainbow == max_size:
            break

        # 블록 그룹 제거
        for y, x in max_positions:
            board[y][x] = -2
        score += max_size ** 2

        # 중력
        down(n, board)

        # 회전
        new_board = [[0]*n for _ in range(n)]
        for y in range(n):
            for x in range(n):
                new_board[y][x] = board[x][n-y-1]
        board = new_board

        # 중력
        down(n, board)

    print(score)

def bfs(y, x, n, visited, board, num):
    dy, dx = [1, -1, 0, 0], [0, 0, 1, -1]
    positions = []
    rainbow = 0
    visited[y][x] = 1
    q = deque([[y, x]])
    while q:
        cy, cx = q.popleft()
        positions.append([cy, cx])
        if board[cy][cx] == 0:
            rainbow += 1
        for d in range(4):
            ny, nx = cy+dy[d], cx+dx[d]
            if 0<=ny<n and 0<=nx<n:
                if not visited[ny][nx] and (board[ny][nx] == 0 or board[ny][nx] == num):
                    visited[ny][nx] = 1
                    q.append([ny, nx])
    # 무지개 visited = 0
    for y in range(n):
        for x in range(n):
            if board[y][x] == 0:
                visited[y][x] = 0
    return positions, rainbow

def down(n, board):
    for x in range(n):
        for y in range(n-1, -1, -1):
            if board[y][x] == -2:
                ny, nx = get_pos(y, x, board)
                if 0<=ny and 0<=nx:
                    board[y][x], board[ny][nx] = board[ny][nx], board[y][x]

def get_pos(y, x, board):
    while True:
        y -= 1
        if y < 0:
            return -1, -1
        if board[y][x] >= 0:
            return y, x
        elif board[y][x] == -1:
            return -1, -1

solution()