BAEKJUN 21609 상어 중학교

문제 링크: https://www.acmicpc.net/problem/21609

요약: 게임의 규칙대로 오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.

2차원 배열을 탐색하고, 중력이라는 시스템으로 내부 값들을 이리저리 옮겨야 하는 전형적인 시물레이션 문제이다.

시물레이션 문제는 조건을 확실히 하는 것이 중요하다.

블록 그룹의 정의

- 인접한 블록의 집합 
  - 일반블록이 적어도 하나 필요
  - 일반 블록의 색은 모두 같아야함
  - 검은색 블록은 포함하면 안됨
  - 무지개 블록은 여러개 있을 수 있음
  - 총 블록수는 2 이상이어야함
- 그룹의 메인 블록
  - 무지개 블록이 아닌 블록
    - 1 순위 행의 번호가 가장 작은 블록
    - 2 순위 열의 번호가 가장 작은 블록

다음 중요한 포인트는 중력이 작용하는 방식이다.

중력 작용
- 검은색 블록을 제외, 모든 블록이 행의 번호가 큰칸으로 이동
- 다른 블록이나 격자의 경계를 만나기 전까지 계속 이동

게임의 순서는 다음과 같다.

1. 크기가 가장 큰 블록 그룹을 찾는다. (기준은 다음과 같음)
  - 블록 크기
  - 무지개 블록 수
  - 메인 블록 행이 가장 큰 것
  - 메인 블록 열이 가장 큰 것
2. 1에서 찾은 블록 그룹의 모든 블록(B개) 제거 (B^2의 점수 획득)
3. 격자에 중력 작용
4. 90도 반시계 방향 회전
5. 다시 격자에 중력이 작용

1. 크기가 가장 큰 그룹을 찾기 위해 BFS 알고리즘을 이용한다.
   • 탐색되지 않은 지점들을 시작으로, 전체 격자를 탐색
   • 가장 큰 그룹을 선택
   • 주의할점은 무지개 블록은 새로운 그룹 탐색전 재방문이 가능하도록 조건을 초기화 해주어야한다는 점이다.
2. 가장 큰 그룹에 속한 블럭들을 제거
3. 중력 적용, 회전, 다시 중력 적용
   • 특수한 알고리즘이 필요하기 보단, 조건에 맞추어 값을 이동시켜주면 된다.

이를 구현한 코드는 다음과 같다.

전체 코드

"""
Author:
    Name: KyungHyun Lim
    Email: lkh1075@gmail.com
"""

from collections import deque

def rotation(N, board):
    nemo_cnt = N // 2
    sx, sy, ex, ey = 0, 0, N-1, N-1
    length = N - 1
    for nemo in range(nemo_cnt):
        #print(sx, sy, ex, ey, length)

        backup = [board[sx][sy + i] for i in range(length)]
        for i in range(length): board[sx][sy + i] = board[sx + i][ey]
        for i in range(length): board[sx + i][ey] = board[ex][ey - i]
        for i in range(length): board[ex][ey - i] = board[ex - i][sy]
        for i in range(length): board[ex - i][sy] = backup[i]

        length -= 2
        sx, sy = sx + 1, sy + 1
        ex, ey = sx + length, sy + length

def apply_gravity(N, board):
    for i in range(N-2, -1, -1):
        for j in range(N):
            if board[i][j] != -1:
                tmp = i
                while tmp + 1 < N and board[tmp+1][j] == -5:
                    board[tmp+1][j] = board[tmp][j]
                    board[tmp][j] = -5
                    tmp += 1

def remove_block(board, block_info):
    for x, y in block_info['blocks']:
        board[x][y] = -5

def search(N, board, visited, x, y):
    dx, dy = [[0, 0, 1, -1], [-1, 1, 0, 0]]

    q = deque()
    q.append((x, y))

    color = board[x][y]

    blocks = [(x, y)]
    rainbows = []

    while q:
        cur_x, cur_y = q.popleft()

        for d in range(4):
            nx, ny = cur_x + dx[d], cur_y + dy[d]
            if 0 <= nx < N and 0 <= ny < N:
                # 방문한적 없고, 무지개 색이나 타겟 색일 경우
                if (not visited[nx][ny]) and (board[nx][ny] in [0, color]):
                    q.append((nx, ny))
                    visited[nx][ny] = True
                    # 그룹에 포함된 무지개색 블록 따로 저장
                    if board[nx][ny] == 0: 
                        rainbows.append((nx, ny))
                    else:
                        # 그룹에 포함된 일반 블록 저장
                        blocks.append((nx, ny))

    for x, y in rainbows:
        visited[x][y] = False

    return rainbows, blocks
    
def find_block(N, board):
    visited = [[False]*N for _ in range(N)]

    big_block = {
        "size": 0,
        "rainbow_size": 0,
        "main_col": 0,
        "main_row": 0,
        "blocks": []
    }
    for i in range(N):
        for j in range(N):
            # 그룹에 포함(방문하지) 않았고, 검은색 또는 무지개색이 아니면
            if (not visited[i][j]) and (board[i][j] not in [-1, 0, -5]):
                flag = False
                visited[i][j] = True
                rainbows, blocks = search(N, board, visited, i, j)
            
                rainbow_counts = len(rainbows)
                whole_counts = len(blocks) + rainbow_counts
                col, row = sorted(blocks)[0]

                if big_block['size'] < whole_counts:
                    flag = True
                elif big_block['size'] == whole_counts:
                    if big_block['rainbow_size'] < rainbow_counts:
                        flag = True
                    elif big_block['rainbow_size'] == rainbow_counts:
                        if big_block['main_col'] < col:
                            flag = True
                        elif big_block['main_col'] == col:
                            if big_block['main_row'] < row:
                                flag=True
                
                if flag:
                    big_block['size'] = whole_counts
                    big_block['rainbow_size'] = rainbow_counts
                    big_block['main_col'] = col
                    big_block['main_row'] = row
                    big_block['blocks'] = blocks + rainbows
    
    return big_block

def debug(board):
    for item in board:
        print(item)

def solution():
    # 격자 크기, 색상 개수
    answer = 0
    N, M = map(int, input().split())

    board = []
    for _ in range(N):
        board.append(list(map(int, input().split())))

    while True:
        block_info = find_block(N, board) # 큰 블록 찾기
        # print(block_info)
        # print('-'*100)
        
        if block_info['size'] <= 1: # 블록이 존재할때 까지 반복
            break
        answer += (block_info['size']**2)
        
        remove_block(board, block_info) # 블록 제거

        # debug(board)
        # print('-'*50)

        apply_gravity(N, board) # 중력 작용

        # debug(board)
        # print('-'*50)

        rotation(N, board) # 90도 반시계 회전S

        # debug(board)
        # print('-'*50)

        apply_gravity(N, board) # 중력 작용

        # debug(board)
        # print('-'*50)
        
    return answer

if __name__ == "__main__":
    answer = solution()
    print(answer)
    
    # gravity test
    # board = [
    #     [2, 1, 2, 3, 4],
    #     [2, 1, -5, -5, 4],
    #     [-5, -5, 2, 3, -5],
    #     [-5, -1, -5, -1, -1],
    #     [-5, -5, -5, -5, -5],
    # ]
    # apply_gravity(5, board)
    # debug(board)