[백준] 21609 - 상어 중학교 (Python)

문제 출처 :

www.acmicpc.net/problem/21609

21609번: 상어 중학교

문제 풀이 :

• 삼성전자 2021 상반기 오전 2번 문제이다. 1번 문제와는 난이도 차이가 있다고 생각한다.
  
  이 문제 또한 BFS,DFS를 섞은 구현문제이다. 하지만 21608 상어 초등학교보다 조건이 더 까다롭다.
• 문제를 보고 구현해야 하는 부분을 먼저 생각해보았다.
  
  1. 오토 플레이 시작과 끝 -> while 문을 통해 블록 그룹이 더 이상 없을 때까지 진행한다.
  2. 가장 큰 블록 그룹 찾기
     -> DFS, BFS 방법을 통해서 가장 큰 블록 그룹을 찾는다.
     -> 가장 큰 블록 그룹이 여러개인 상황에 대한 조건 처리를 잘해줘야한다. 그런경우엔
     1) 무지개 블록 갯수가 많은거
     2) 기준 블록의 행이 가장 큰거
     3) 기준 블록의 열이 가장 큰거
     -> 이 조건을 고려해야하기 때문에 가장 큰 블록 그룹을 찾을때 해당 그룹 블록의 기준 블록과 무지개 블록의 갯수를 알고 있어야한다.
  3. 2에서 찾은 블록그룹 제거하고 점수 계산
  4. 중력 적용하는 함수
  5. 90도 반시계 회전 함수
• 구현해야하 하는 함수는 2,3,4,5 정도로 4개 정도 된다. 함수로 각각 구현하는 이유는 디버깅이 편리하기 때문이다.
  
  4번은 아마 모노미노도미노2 문제를 풀어봤다면 쉽게 구현할 수 있을 것이다.
  5번 또한 Python의 경우 쉽게 구현할 수 있다. 행렬에 대한 Transpose, 좌우 회전은 문제에서 자주 나오니 코드를 외워두면 더 좋다. (외우지 않더라도 index를 잘 생각해서 구현하면 큰 어려움이 없기도 하다.)
  필자의 경우는 2,3에서 많이 헤맸다.
  
  
• 블록그룹을 찾는 함수를  catch_block으로 , 그중 가장 큰 블록그룹을 찾아서 점수를 계산하는걸 max_area 함수로 구현하였다.
  
  catch_block 같은 경우 maps에서 colar block을 입력으로 받으면 dfs를 수행해서 블록 그룹의 크기, 블록들, 무지개 블록의 갯수, 기준 블록을 output으로 내보내준다.
  
  max_area 는 catch_block을 모든 color block에 대해서 수행하며 max에 대한 값을 갱신한다. 필자의 경우 점수를 얻을때 block을 없애야 해서 없어지는 블록 그룹에 '-'을 넣어주었다. (이거때문에 엄청 헤맸는데, '-'도 따로 처리해주지 않으면 python에서는 자동 형 변환을 통해 숫자로 값을 받아서 진행된다. 앞으론 이런 실수 하지 않도록 주의해야겠다.) max 값을 갱신할땐 문제에 주어진 조건 1),2),3)을 잘 고려해서 짜야한다.
  21608번 처럼 큰값에서 작은 값을 넣는것으로 해결 할 수 없는 문제이다. 왜냐하면 기준 블록을 정할때는 행,열이 작은 순서로 정하지만 , 블록그룹에서는 기준 블록의 행,열에 대해서 큰 값대로 정하기 때문이다.
  
  
  

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

def catch_block(s):
    global maps,n
    area = 1
    visited=[[0]*n for _ in range(n)]
    color = maps[s[0]][s[1]]
    blocks = [(s[0],s[1])]
    stack = [s]
    visited[s[0]][s[1]]=1
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    r_b = []
    num_rainbow  = 0
    while(stack):
        cur_x,cur_y =stack.pop()
        for i in range(4):
            nx = cur_x+dx[i]
            ny = cur_y+dy[i]
            if(nx>=n or ny>=n or nx<0 or ny<0):
                continue
            if(visited[nx][ny]==0):
                visited[nx][ny]=1
                if(maps[nx][ny]!='-'):
                    if(maps[nx][ny]==color or maps[nx][ny]==0):
                        if(maps[nx][ny]==0):
                            num_rainbow +=1
                        blocks.append((nx,ny))
                        stack.append((nx,ny))
                        area+=1
    if(area>=2):
        blocks = sorted(blocks,key=lambda x : (x[0],x[1]))
        for i in blocks:
            if(maps[i[0]][i[1]]!=0):
                r_b = [i[0],i[1]]
                break
        return area,blocks,num_rainbow,r_b
    else:
        return 0,[],0,[-1,-1]


def max_area():
    global maps,n

    max_area =0
    b = []
    max_rainbow=-1
    r_b = [-1,-1]
    score =0
    temp_area = 0
    temp_blocks =[]
    temp_rainbow=0
    temp_r_b = [-1,-1]

    for j in range(n):
        for i in range(n):
            if(maps[i][j]!=-1 and maps[i][j]!='-' and maps[i][j]!=0):
                temp_area ,temp_blocks,temp_rainbow,temp_r_b = catch_block((i,j))
                if(temp_area>max_area):
                    max_area=temp_area
                    b=temp_blocks
                    max_rainbow = temp_rainbow
                    r_b = temp_r_b
                elif(temp_area==max_area):
                    if(temp_rainbow>max_rainbow):
                        max_rainbow=temp_rainbow
                        b=temp_blocks
                        max_area = temp_area
                        r_b = temp_r_b
                    elif(temp_rainbow == max_rainbow):
                        if(temp_r_b[0]>r_b[0]):
                            b= temp_blocks
                            #max_area =temp_area
                            #max_rainbow = temp_rainbow
                            r_b = temp_r_b
                        elif(temp_r_b[0]==r_b[0]):
                            if(temp_r_b[1]>r_b[1]):
                                b= temp_blocks
                                #max_area =temp_area
                                #max_rainbow = temp_rainbow
                                r_b = temp_r_b
    for i,j in b:
        maps[i][j]='-'
    score = max_area**2
    return score,b

def show_maps():
    global maps,n
    for i in range(n):
        for j in range(n):
            print(maps[i][j],end='\t')
        print()

def gravity():
    global maps,n
    for j in range(n):
        for i in range(n-1,-1,-1):
            if(maps[i][j]!=-1 and maps[i][j]!='-'):
                cur_val = maps[i][j]
                maps[i][j]='-'
                cur_loc = i
                while(True):
                    if(cur_loc==n-1):
                        maps[cur_loc][j]=cur_val
                        break
                    n_loc = cur_loc+1
                    if(n_loc==n-1):
                        if(maps[n_loc][j]=='-'):
                            maps[n_loc][j]=cur_val
                            break
                        else:
                            maps[cur_loc][j]=cur_val
                            break
                    else:
                        if(maps[n_loc][j]!='-'):
                            maps[cur_loc][j]=cur_val
                            break
                    cur_loc = n_loc


def rotation_mat():
    global maps,n
    res = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            res[n-j-1][i]=maps[i][j]
    maps = res


ans = 0
while(True):
    temp_score,b = max_area()
    #print(temp_score,b)
    if(temp_score>0):
        ans+= temp_score
    else:
        break
    #show_maps()
    #print()
    gravity()
    #show_maps()
    #print()
    rotation_mat()
    #show_maps()
    #print()
    gravity()
    #show_maps()
    #print()

print(ans)