이번 문제는 삼성 기출 문제로, 2차원 배열의 회전과 BFS, 배열 한쪽으로 밀어내기를 이용하여 해결하였다. 각각의 기능을 함수로 모듈화하여 해결하였고, 함수명은 다음과 같다

• bfs(y, x):
  블록 그룹을 찾고, 속하는 무지개색 블록의 갯수와 해당 그룹의 모든 인덱스를 리스트로 반환
• rmv(path):
  bfs함수를 통해 반환된 모든 인덱스의 리스트를 순회하며 해당 인덱스의 값을 지우는 함수
• gravity():
  2차원 리스트의 값들을 아래로 밀어내리는 함수
• cycling():
  2차원 리스트를 반시계 방향으로 90도 회전시키는 함수

gravity()함수를 구현하는데에 많은 시간이 걸렸다. -1 블록의 경우에는 위치를 고정시켜야하기 때문이었다. 이는 다음에 탐색할 값이 -2(비어있는 칸)을 나타낼 때에만 값을 교체하도록 하여 해결하였다.

그리고 bfs함수를 호출할 때에 방문처리된 인덱스 중 무지개색 블록의 경우에는 다시 방문처리를 취소해야 했다. 그 이유는 해당 인덱스는 모든 색에서 연결이 가능하기 때문에 다음 순회하는 색에 대한 탐색이 불가능하게 되기 때문이었다.

Code

import collections
import copy
n, m=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
def bfs(y, x):
    q=collections.deque()
    q.append((y, x))
    rainbows=0
    path=[(y, x)]
    block=grid[y][x]
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<n and not visited[ny][nx] and grid[ny][nx]>=0:
                if grid[ny][nx]==0:
                    rainbows+=1
                    path.append((ny, nx))
                    visited[ny][nx]=True
                    q.append((ny, nx))
                elif grid[ny][nx]==block:
                    visited[ny][nx]=True
                    path.append((ny, nx))
                    q.append((ny, nx))
    return (rainbows, path)

def rmv(path):
    for y, x in path:
        grid[y][x]=-2

def gravity():
    for i in range(n-2, -1, -1):
        for j in range(n):
            if grid[i][j]>-1:
                r=i
                while True:
                    if 0<=r+1<n and grid[r+1][j]==-2:
                        grid[r+1][j]=grid[r][j]
                        grid[r][j]=-2
                        r+=1
                    else:
                        break

def cycling():
    global grid
    tmp=[[-2 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            tmp[n-1-j][i]=grid[i][j]
    grid=copy.deepcopy(tmp)

answer=0
while True:
    visited = [[False for _ in range(n)] for _ in range(n)]
    answers=[]
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and grid[i][j]>0:
                visited[i][j]=True
                r, p=bfs(i, j)
                for rr in range(n):
                    for cc in range(n):
                        if grid[rr][cc]==0 and visited[rr][cc]:
                            visited[rr][cc]=False
                if len(p)>=2:
                    answers.append((r, p, i, j))
    if not answers:
        break
    answers.sort(key=lambda x:(len(x[1]), x[0], x[2], x[3]), reverse=True)
    rmv(answers[0][1])
    gravity()
    cycling()
    gravity()
    answer+=len(answers[0][1])**2
print(answer)