이번 문제는 삼성 기출 문제로, 2차원 배열의 회전과 BFS, 배열 한쪽으로 밀어내기를 이용하여 해결하였다. 각각의 기능을 함수로 모듈화하여 해결하였고, 함수명은 다음과 같다
gravity()함수를 구현하는데에 많은 시간이 걸렸다. -1 블록의 경우에는 위치를 고정시켜야하기 때문이었다. 이는 다음에 탐색할 값이 -2(비어있는 칸)을 나타낼 때에만 값을 교체하도록 하여 해결하였다.
그리고 bfs함수를 호출할 때에 방문처리된 인덱스 중 무지개색 블록의 경우에는 다시 방문처리를 취소해야 했다. 그 이유는 해당 인덱스는 모든 색에서 연결이 가능하기 때문에 다음 순회하는 색에 대한 탐색이 불가능하게 되기 때문이었다.
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)