문제

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

나의 코드

"""

"""

from collections import deque

N, M = map(int, input().split()) # N:격자 크기, M:색상의 개수
pan = [ list(map(int, input().split())) for _ in range(N) ]
answer = 0

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def block_search(x, y):
    visited[x][y] = True

    rainbow_block = []
    normal_block = [(x, y)]
    normal_block_color = pan[x][y] # 일반 블록 색 저장 (블록 그룹 내 일반 블록의 색은 같아야 함)

    q = deque([(x, y)])

    while q:
        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]

            if 0 <= mx < N and 0 <= my < N:
                if pan[mx][my] == 0 and not visited[mx][my]:
                    visited[mx][my] = True
                    rainbow_block.append((mx, my))
                    q.append((mx, my))
                elif pan[mx][my] == normal_block_color and not visited[mx][my]:
                    visited[mx][my] = True
                    normal_block.append((mx, my))
                    q.append((mx, my))

    # 무지개 블록은 다음 BFS에서 사용될 수 있으므로 다시 False 처리
    for x, y in rainbow_block:
        visited[x][y] = False

    if len(rainbow_block+normal_block) >= 2: # 그룹에 속한 블록 개수가 2이상인 경우 그룹으로 인정
        normal_block.sort() # 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.
        return len(rainbow_block+normal_block), len(rainbow_block), normal_block[0], normal_block+rainbow_block
    return False

# 검은색 블록(-1)을 제외한 모든 블록이 아래(down)로 이동
def gravity(arr):
    for i in range(N-2, -1, -1): # 바닥부터 탐색
        for j in range(N):
            if arr[i][j] != -1: # 검은색 블록이 아닌 경우
                pointer = i # 현재 위치 행 저장

                # 다음 칸이 바닥이거나, 다른 블록이 존재하는 경우 종료 -> 그게 아니라면 계속 하강
                while pointer + 1 < N and arr[pointer+1][j] == -2:
                    arr[pointer+1][j] = arr[pointer][j]
                    arr[pointer][j] = -2
                    pointer += 1
    return arr

# 배열을 반시계 방향으로 90도 회전하는 코드
def rotate(arr):
    return list(map(list, zip(*arr)))[::-1]

while True:
    visited = [[False] * N for _ in range(N)]

    # 블록 그룹을 찾기 위한 반복문
    block_collection = []
    for i in range(N):
        for j in range(N):
            if pan[i][j] >= 1: # 일반 블록인 경우 탐색(블록 그룹에 일반 블록이 1개 이상 있어야 하므로 일반블록만 탐색)
                res = block_search(i, j)
                if res:
                    block_collection.append(res)

    if not block_collection: # 블록 그룹이 없다면 반복문 종료
        break

    """ 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 
    그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다. 
    라는 조건을 만족하기 위해 내림차순 정렬"""
    block_collection.sort(reverse=True)

    answer += block_collection[0][0] ** 2
    for x, y in block_collection[0][3]:
        pan[x][y] = -2 # 점수로 없어진 칸은 -2로 채움

    # 중력
    pan = gravity(pan)
    # 반시계 방향 90도 회전
    pan = rotate(pan)
    # 중력
    pan = gravity(pan)

print(answer)
    

설명

배열의 반시계방향 90도 회전과, 중력 구현하는 법, BFS내의 무지개 블록은 다시 False 처리하는 법 등등 다시 봐야 함.

참고 자료

https://velog.io/@mmy789/Python-zip-%EC%9D%B4%EC%9A%A9%ED%95%B4%EC%84%9C-2%EC%B0%A8%EC%9B%90-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%ED%9A%8C%EC%A0%84%ED%95%98%EA%B8%B0#1-%EC%8B%9C%EA%B3%84-%EB%B0%A9%ED%96%A5%EC%9C%BC%EB%A1%9C-%ED%9A%8C%EC%A0%84