상어 중학교 파이썬 백준 21609

문제

input

첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.

둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.

output

첫째 줄에 획득한 점수의 합을 출력한다.

TODO

가장 큰 그룹 찾기 
	->이미 방문한 좌표를 처리할 때 0은 계속 사용 가능 
    ->그룹을 못찾으면 return False 
    ->대표는 어차피 위왼->아오 순이니까 처음들어온게 대표
    -> 우선순위 무지개 -> 하 -> 우
    -> 무지개 개수 같다면 마지막에 들어온게 우선순위 높음 
그룹 지우기 
	->점수 계산
중력 -> rotate -> 중력

CODE

import sys 

n,m = map(int, sys.stdin.readline().split()) 
world = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
rain_position = []

from collections import deque 
dx = [0,1,-1,0]
dy = [1,0,0,-1]
answer = 0 
def search_max(n): 
    global answer 
    q = deque()
    check = [[True for _ in range(n)] for _ in range(n)]
    ret = []
    maxi_rain = 0 
    succ = False 
    rain_position = [] 
    for i in range(n):
        for j in range(n):
            if world[i][j] != 0 and world[i][j] != -1 and world[i][j] != -2 and check[i][j] : 
                q.append((i,j)) 
                check[i][j] = False 
                save = deque()
                save.append((i,j))
                rain_cnt = 0 
                while q:
                    x,y = q.popleft()
                    for px,py in zip(dx,dy): 
                        nx,ny = x+px,y+py 
                        if 0<=nx<n and 0<=ny<n and check[nx][ny] and (world[i][j] == world[nx][ny] or world[nx][ny] == 0) : 
                            q.append((nx,ny)) 
                            save.append((nx,ny)) 
                            check[nx][ny] = False 
                            if world[nx][ny] == 0 :
                                rain_cnt+=1 
                                rain_position.append((nx,ny))
                len_save = len(save)
                if len_save >= 2 : 
                    succ = True 
                    if len_save > len(ret) : 
                        ret = [s for s in save]
                        maxi_rain = rain_cnt
                    elif len_save == len(ret) and maxi_rain <= rain_cnt: 
                        ret = [s for s in save]
                        maxi_rain = rain_cnt
                for rx,ry in rain_position : 
                    check[rx][ry] = True
    if succ : 
        answer += len(ret) ** 2 
        for x,y in ret : 
            world[x][y] = -2 
    return succ 

def gravity_d(n):
    for i in range(n):
        height = n-1 
        for j in range(n-1,-1,-1): 
            if world[j][i] == -2 :
                continue 
            elif world[j][i] == -1 : 
                height = j -1  
            else :
                world[height][i], world[j][i] = world[j][i],world[height][i]
                height -= 1 

def rotate(n): 
    ret = [[0 for _ in range(n)] for _ in range(n)] 
    global world 
    for i in range(n):
        for j in range(n): 
            ret[n-1-j][i] = world[i][j]
    world = ret 

while search_max(n): 
    gravity_d(n)
    rotate(n)
    gravity_d(n) 
    # for w in world:
    #     print(w)
print(answer)

회고

배열 돌리고 내리고 난리난 문제.
우선순위 처리하기는 쉬운데 확신이 없었다.