백준 21609 상어중학교

import copy
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]

def grouping(g):
    blockgroup = []
    start = copy.deepcopy(g)
    for i in range(n):
        for j in range(n):
            if 1 <= start[i][j] <= m:
                # 여기서부터 탐색
                check = [[-1] * n for _ in range(n)]
                q = deque()
                q.append((i, j))
                check[i][j] = 0
                rainbow = 0
                while q:
                    x, y = q.popleft()
                    for d in range(4):
                        nx, ny = x + dx[d], y + dy[d]
                        if nx < 0 or ny < 0 or nx >= n or ny >= n:
                            continue
                        if check[nx][ny] == -1:
                            if g[nx][ny] == g[i][j]:
                                q.append((nx, ny))
                                check[nx][ny] = 0
                                start[nx][ny] = -3
                            if g[nx][ny] == 0:
                                q.append((nx, ny))
                                check[nx][ny] = 0
                                rainbow += 1
                cnt = 0
                for u in range(n):
                    for v in range(n):
                        if check[u][v] == 0:
                            cnt += 1
                if cnt >= 2:
                    blockgroup.append((cnt, rainbow, i, j))
      
    return blockgroup

def delete(blockgroup, g):
    blockgroup.sort(reverse=True)
    cnt, rainbow, sx, sy = blockgroup[0]
    check = [[-1] * n for _ in range(n)]
    bnum = g[sx][sy]
    g[sx][sy] = -2
    q = deque()
    q.append((sx, sy))
    check[sx][sy] = 0
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if check[nx][ny] == -1:
                if g[nx][ny] == bnum or g[nx][ny] == 0:
                    q.append((nx, ny))
                    check[nx][ny] = 0
                    g[nx][ny] = -2
    score = cnt * cnt
    return score, g


def gravity(g):
    for y in range(n):
        for x in range(n-2, -1, -1):
            if g[x][y] < 0:
                continue
            while True:
                nx = x + 1
                if nx >= n or g[nx][y] != -2:
                    break
                g[x][y], g[nx][y] = g[nx][y], g[x][y]
                x = nx
    return g

def rotate(g):
    tmp_g = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            tmp_g[i][j] = g[j][n-1-i]
    return tmp_g

ans = 0

while True:
    blockgroup = grouping(g)
    if len(blockgroup) == 0:
        break
    score, g = delete(blockgroup, g)
    ans += score
    g = gravity(g)
    g = rotate(g)
    g = gravity(g)

print(ans)

!!

from collections import deque
import copy
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def find_group(g):
    blockgroup = []
    visited = [[False] * n for _ in range(n)]
    rainbow = 0
    for i in range(n):
        for j in range(n):
            if visited[i][j] == False and g[i][j] >= 1:
                tmp_blockgroup = []
                check = [[False] * n for _ in range(n)]
                tmp_rainbow = 0
                q = deque()
                q.append((i, j))
                check[i][j] = True
                visited[i][j] = True
                tmp_blockgroup.append((i, j))
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        if nx < 0 or ny < 0 or nx >= n or ny >= n or g[nx][ny] < 0:
                            continue
                        if g[nx][ny] == 0 and check[nx][ny] == False:
                            tmp_rainbow += 1
                            q.append((nx, ny))
                            check[nx][ny] = True
                            tmp_blockgroup.append((nx, ny))
                        if g[nx][ny] == g[i][j] and check[nx][ny] == False:
                            visited[nx][ny] = True
                            q.append((nx, ny))
                            check[nx][ny] = True
                            tmp_blockgroup.append((nx, ny))
                if len(tmp_blockgroup) < 2:
                    continue
                if len(blockgroup) < len(tmp_blockgroup):
                    blockgroup = copy.deepcopy(tmp_blockgroup)
                elif len(blockgroup) == len(tmp_blockgroup):
                    if rainbow < tmp_rainbow:
                        blockgroup = copy.deepcopy(tmp_blockgroup)
                        rainbow = tmp_rainbow
                    elif rainbow == tmp_rainbow:
                        tmp_blockgroup.sort()
                        blockgroup.sort()
                        tx, ty = tmp_blockgroup[0]
                        bx, by = blockgroup[0]
                        if tx < bx:
                            blockgroup = copy.deepcopy(tmp_blockgroup)
                        elif tx == bx:
                            if ty < by:
                                blockgroup = copy.deepcopy(tmp_blockgroup)
    score = len(blockgroup) ** 2
    if len(blockgroup) == 0:
        return False, g, score
    for x, y in blockgroup:
        g[x][y] = -2                    
    return True, g, score

def gravity(g):
    for i in range(n):
        for j in range(n-2, -1, -1):
            if g[j][i] < 0:
                continue
            for k in range(j+1, n):
                if g[k][i] != -2:
                    break
                g[k][i], g[k-1][i] = g[k-1][i], g[k][i]
    return g

def rotate(g):
    g_tmp = [[-2] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            g_tmp[i][j] = g[j][n-1-i]
    return g_tmp


ans = 0
while True:
    bool, g, score = find_group(g)
    if bool == False:
        break
    ans += score
    g = gravity(g)
    g = rotate(g)
    g = gravity(g)

print(ans)

얘는 왜 안되는지 생각해보기

from collections import deque
import copy
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def find_group(g):
    # 최종 반환할 것을 blockgroup에 넣었습니다
	# visited 에 일반 블록 중 시작 불가능지점(False)를 표시했습니다.
    blockgroup = []
    visited = [[True] * n for _ in range(n)]
    rainbow = 0
    for i in range(n):
        for j in range(n):
			# 일반 블럭 중 시작 가능한 지점에서 시작
            if visited[i][j] == True and g[i][j] >= 1:
				#bfs해서 비교 대상 블럭 그룹을 만들었습니다. check는 bfs를 돌때 방문표시를 위해 만들어줬습니다.
                tmp_blockgroup = []
                check = [[False] * n for _ in range(n)]
                tmp_rainbow = 0
                q = deque()
                q.append((i, j))
                check[i][j] = True
                visited[i][j] = False
                tmp_blockgroup.append((i, j))
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
						# 이동할 곳이 경계를 벗어나거나 -1(검은블럭) 또는 -2(빈칸) 일 때 
                        if nx < 0 or ny < 0 or nx >= n or ny >= n or g[nx][ny] < 0:
                            continue
						# 이동할 곳이 무지개 블럭일 때 
                        if g[nx][ny] == 0 and check[nx][ny] == False:
                            tmp_rainbow += 1
                            q.append((nx, ny))
                            check[nx][ny] = True
                            tmp_blockgroup.append((nx, ny))
						# 이동할 곳이 일반 블럭일 때, visited도 시작 불가능(False)로 표시
                        if g[nx][ny] == g[i][j] and check[nx][ny] == False:
                            visited[nx][ny] = False
                            q.append((nx, ny))
                            check[nx][ny] = True
                            tmp_blockgroup.append((nx, ny))
				# tmp_blockgroup을 다 만들고 길이를 판별해서 2보다 작으면 continue 처리
                if len(tmp_blockgroup) < 2:
                    continue
				# 블럭 갯수 비교 -> 만약 tmp 가 더 크다면 블럭 그룹을 갱신
                if len(blockgroup) < len(tmp_blockgroup):
                    blockgroup = copy.deepcopy(tmp_blockgroup)
				# 블럭 갯수가 같은 경우 rainbow 비교 후 갱신, rainbow 같이 갱신
                elif len(blockgroup) == len(tmp_blockgroup):
                    if rainbow < tmp_rainbow:
                        blockgroup = copy.deepcopy(tmp_blockgroup)
                        rainbow = tmp_rainbow
					# rainbow 갯수도 같다면 tmp_blockgroup 과 blockgroup을 sort해서 좌표를 작은 것부터 정렬 후 비교해줬습니다.
                    elif rainbow == tmp_rainbow:
                        tmp_blockgroup.sort()
                        blockgroup.sort()
                        tx, ty = tmp_blockgroup[0]
                        bx, by = blockgroup[0]
                        if tx < bx:
                            blockgroup = copy.deepcopy(tmp_blockgroup)
                        elif tx == bx:
                            if ty < by:
                                blockgroup = copy.deepcopy(tmp_blockgroup)
	# return할 점수 값 계산
    score = len(blockgroup) ** 2
	# 만약 블럭 그룹이 더이상 만들어지지 않는다면 False 값을 반환해서 밑에 while 문을 탈출
    if len(blockgroup) == 0:
        return False, g, score
	# 최종적으로 블럭그룹이 된 좌표들을 빈칸(-2)로 만들어줌
    for x, y in blockgroup:
        g[x][y] = -2                    
    return True, g, score
#중력 코드
def gravity(g):
	# 열 별로 
    for i in range(n):
		# 행 별로 행의 번호가 큰 부분부터 아래로 내려줌
        for j in range(n-2, -1, -1):
			# 만약 그 행이 -1(검은색)이거나 -2(빈칸)일 때는 그냥 둔다
            if g[j][i] < 0:
                continue
			# 해당 해보다 아랫쪽(행 번호가 큰 부분)을 검사해서 빈칸이라면 바꿔주고 아니라면 반복문을 탈출해준다
            for k in range(j+1, n):
                if g[k][i] != -2:
                    break
                g[k][i], g[k-1][i] = g[k-1][i], g[k][i]
    return g
# 회전 코드
def rotate(g):
	# 결과로 반환할 g_tmp
    g_tmp = [[-2] * n for _ in range(n)]
	# 행은 열과 바꾸고 열은 끝에서부터 바꾸어줍니다
    for i in range(n):
        for j in range(n):
            g_tmp[i][j] = g[j][n-1-i]
    return g_tmp
# 아까 블럭그룹이 0개라면 False를 반환하여 while문을 탈출하고 결과를 냅니다.
ans = 0
while True:
    bool, g, score = find_group(g)
    if bool == False:
        break
    ans += score
    g = gravity(g)
    g = rotate(g)
    g = gravity(g)
print(ans)