import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]
def BFS(y,x,color):
dq = deque()
dq.append((y,x))
result = set()
rainbow = set()
while dq:
y,x = dq.popleft()
if visited[y][x]:
continue
visited[y][x] = 1
if matrix[y][x] == -2:
rainbow.add((y,x))
result.add((y,x))
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and N>x1>=0:
if visited[y1][x1]:
continue
if matrix[y1][x1] == color or matrix[y1][x1] == -2:
dq.append((y1,x1))
rainbowcnt = len(rainbow)
for y,x in rainbow:
visited[y][x] = 0
return result,rainbowcnt
def largegroup():
maxresult,maxrainbowcnt = set(),0
for i in range(N):
for j in range(N):
if not visited[i][j] and matrix[i][j] > 0:
result,rainbowcnt = BFS(i,j,matrix[i][j])
if len(result)>len(maxresult) or (len(result)==len(maxresult) and rainbowcnt>=maxrainbowcnt):
maxresult,maxrainbowcnt = result,rainbowcnt
return maxresult
def ccw():
newmatrix = [[0]*N for i in range(N)]
for i in range(N):
for j in range(N):
newmatrix[N-j-1][i] = matrix[i][j]
return newmatrix
def down(y,x):
v = matrix[y][x]
matrix[y][x] = 0
while True:
if y+1==N or matrix[y+1][x]:
break
y += 1
matrix[y][x] = v
def gravity():
for x in range(N):
for y in reversed(range(N)):
if matrix[y][x] and matrix[y][x] != -1:
down(y,x)
N,M = map(int,input().split())
matrix = []
for i in range(N):
matrix.append([*map(lambda x:-2 if not x else x,map(int,input().split()))])
result = 0
while True:
visited = [[0]*N for i in range(N)]
largest = largegroup()
if len(largest) < 2:
break
result += len(largest)**2
for y,x in largest:
matrix[y][x] = 0
gravity()
matrix = ccw()
gravity()
print(result)
딱히 어려울건 하나도 없는 문제인데 작성해야하는 코드양이 무지막지하게 긴 문제이다.
풀이방법은 지문에서 다 제시해주기 때문에 그냥 지문 그대로 차근차근 작성하면 된다. 이때 주의할 점 몇가지만 소개하면
1. 블록의 길이가 2 이상이어야 한다는 점.
2. 블록의 크기가 같고 무지개블록의 개수가 같은 경우 "행과 열이 큰 것을 골라야한다는 점"
을 주의해야 한다.
이외 나머지는 그냥 지문에서 시키는대로 하면 된다.
오늘의 교훈) 그냥 무지성 구현은 재미가 없는것 같다.