Baek_21609

이 문제도 삼전코테 준비중에 풀었던 문제이다.

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
score = 0
group = list()


def find_group(x, y):
    dq = deque([(x, y)])
    vis = {(x, y)}
    num = matrix[x][y]
    rainbow = 0
    global group
    while dq:
        a, b = dq.popleft()
        for n, m in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            an, bm = a+n, b+m
            if 0 <= an < N and 0 <= bm < N and (an, bm) not in vis and (matrix[an][bm] == 0 or matrix[an][bm] == num):
                dq.append((an, bm))
                vis.add((an, bm))
                if matrix[an][bm] == 0:
                    rainbow += 1
    if len(vis) > 1:
        group.append((len(vis), rainbow, (x, y), vis))
    return vis


def destroy_group(group):
    for i, j in group:
        matrix[i][j] = ''


def gravity():
    for i in range(N-1, -1, -1):
        for j in range(N):
            if matrix[i][j] == '':
                k = i
                while k >= 0:
                    if matrix[k][j] == '':
                        k -= 1
                    elif matrix[k][j] >= 0:
                        matrix[i][j] = matrix[k][j]
                        matrix[k][j] = ''
                        break
                    else:
                        break


def turn_matrix():
    global matrix
    new_matrix = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            new_matrix[i][j] = matrix[j][N-i-1]
    matrix = new_matrix


def solve():
    global group
    global score
    visit = set()
    while True:
        for i in range(N):
            for j in range(N):
                if matrix[i][j] != '' and matrix[i][j] > 0 and (i, j) not in visit:
                    v = find_group(i, j)
                    visit.update(v)
        if not group:
            break
        group.sort()
        gr = group.pop()
        destroy_group(gr[3])
        score += gr[0]**2
        gravity()
        turn_matrix()
        gravity()
        group = list()
        visit = set()
    print(score)

삼전 문제를 준비하며 필요 함수들을 만들고 차근차근 실행하는 습관이 키워졌다ㅋㅋ
1. 블로 그룹 찾고 제거, 점수 누적
2. 중력작용
3. 반시계 방향 회전
4. 중력작용

그래프이론이 필요한 문제고 난 요즘 항상 bfs를 애용한다.
문제는 다행히 잘 맞췄다.
차근차근이 핵심인 것 같다.