1. 아이디어
문제에서 제시된 내용대로 따라 구현하면된다. 블록 그룹의 경우 딕셔너리를 활용했다. key는 블록 그룹의 기준 블록을 가리키는 좌표이고 value는 해당 그룹에 속하는 블록들의 좌표들이 들어있는 리스트이다. 격자의 (0,0) 부터 (n-1, n-1)까지 순차적으로 탐색한다. 탐색을 하면서 해당 좌표가 일반 블록이고 처음 방문하는 것이라면, key로 들어가는 기준 블록은 항상 기준 블록의 조건을 만족한다.
무지개 블록의 경우, 1개의 무지개 블록은 여러개의 블록 그룹에 소속될 수 있다. 따라서, 블록 그룹을 만든 후, 방문 처리된 무지개 블록의 좌표를 방문 처리하지 않은 것으로 설정한다.
위의 과정으로부터 형성된 블록 그룹 중, 기준 블록만 갖고 있는 블록 그룹들을 모두 제거한다. 그리고 해당 좌표를 방문하지 않는 것으로 설정한다.
블록 그룹을 만드는데 성공했으면, 그 중 가장 큰 블록 그룹을 찾고 문제에 제시된 내용처럼 점수를 구하고 그 부분들을 제거한다. 이후 중력 작용과 90도 반시계 방향 회전, 다시 중력 작용을 하면된다. 이 부분은 그냥 구현이기 때문에 구체적인 설명은 생략한다.
위에서 언급된 과정을 블록 그룹이 하나도 없을 때까지 반복하고, 각 과정에서 얻은 점수를 합산하여 출력한다.
2. 코드
EMPTY = -2
BLACK = -1
RAINBOW = 0
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
groups = {}
answer = 0
def isin(y,x):
if -1<y<n and -1<x<n: return True
return False
def make_groups():
global groups, arr
visited = [[False]*n for _ in range(n)]
for i in range(n):
for j in range(n):
if arr[i][j] in (EMPTY, BLACK, RAINBOW): continue
if not visited[i][j]:
visited[i][j] = True
groups[(i,j)] = []
_make_groups(visited, i, j)
if not groups[(i,j)]: del groups[(i,j)]
visited[i][j] = False
set_rainbow_false(visited)
def _make_groups(visited, sy, sx):
global groups, arr
q = []
q.append((sy, sx))
d = ((1,0), (-1,0), (0,-1), (0,1))
while q:
y, x = q[0]
del q[0]
for dy, dx in d:
ny = y + dy
nx = x + dx
if not isin(ny, nx): continue
if arr[ny][nx] not in (arr[sy][sx], RAINBOW): continue
if not visited[ny][nx]:
visited[ny][nx] = True
groups[(sy,sx)].append((ny, nx))
q.append((ny, nx))
def set_rainbow_false(visited):
global arr
for i in range(n):
for j in range(n):
if arr[i][j] == RAINBOW: visited[i][j] = False
def find_biggest_group():
global groups
k, size = (-1,-1), 0
for key, value in groups.items():
t = len(value)
if size < t+1: k, size = key, t+1
elif size == t+1:
rain1 = get_rainbow_size(k)
rain2 = get_rainbow_size(key)
if rain1 < rain2: k, size = key, t+1
elif rain1 == rain2: k, size = key, t+1
return k, size
def get_rainbow_size(key):
global groups
cnt = 0
for y, x in groups[key]:
if arr[y][x] == RAINBOW: cnt += 1
return cnt
def score():
global groups
key, cnt = find_biggest_group()
arr[key[0]][key[1]] = EMPTY
for y, x in groups[key]: arr[y][x] = EMPTY
return cnt**2
def gravity():
global arr
for x in range(n):
for y in range(n-1, -1, -1):
if arr[y][x] == BLACK: continue
_gravity(y, x)
def _gravity(sy, sx):
global arr
for y in range(sy+1, n):
if arr[y][sx] == EMPTY: arr[y-1][sx], arr[y][sx] = arr[y][sx], arr[y-1][sx]
else: break
def rotate():
global arr
stack = []
for i in range(n):
for j in range(n):
stack.append(arr[i][j])
for x in range(n-1, -1, -1):
for y in range(n):
arr[y][x] = stack.pop()
while True:
groups = {}
make_groups()
if not groups: break
answer += score()
gravity()
rotate()
gravity()
print(answer)
