[python] 백준 21609 상어 중학교

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

 

문제 해결

• 놓치기 쉬운 조건들을 먼저 잘 인지하고 있어야한다.
  • 블록 그룹은 연결된 블록 집합이며 일반 블록이 적어도 한개 이상 있어야하며 색은 모두 같아야한다.(무지개는 무조건 포함가능)
  • 연결된 블록이 가장 많은 블록 집합을 골라야한다. 만약 같은 것이 존재한다면 무지개색이 가장 많은 것을 선택하며 그래도 같으면 기준 블록 행이 가장 큰 것, 그래도 같으면 기준 블록 열이 가장 큰 것을 고르는 것이다.(기준 불록이 블록 정보를 알려주는 리스트(info)의 마지막 인덱스의 첫번째 인덱스 값으로(info[-1][0]) 있으므로 내림차순 정렬을 하면 최후 기준으로 최대 크기의 블록을 선택할 수 있다.)
• 이 조건들을 인지하고 bfs를 사용하여 최대크기의 블록 그룹을 구하여 점수를 더해주고 블록을 빼주면 된다.
• 그 후 중력으로 블록이 내려가는 함수를 구현해야한다.
• 그리고 반시계방향으로 블록이 90도 회전하는 함수를 구현한다.

 

CODE

from collections import deque
def bfs(x,y):
    dxs = [-1,1,0,0]
    dys = [0,0,-1,1]
    que = deque()
    que.append((x,y))
    visited[x][y] = 1
    block_cnt, rainbow_cnt = 1, 0
    blocks, rainbows = [[x,y]], []
    while que:
        a, b = que.popleft()
        for dx, dy in zip(dxs, dys):
            na = a + dx
            nb = b + dy
            if 0<=na<n and 0<=nb<n and visited[na][nb] ==0:
                if (board[na][nb] == board[x][y]) or (board[na][nb] ==0):
                    visited[na][nb] = 1
                    que.append((na,nb))
                    block_cnt += 1
                    if board[na][nb] ==0:
                        rainbow_cnt += 1
                        rainbows.append((na,nb))
                    else:
                        blocks.append((na,nb))
    for x,y in rainbows:
        visited[x][y] = 0 # board[x][y] =0은 공유지로 다음번에도 쓸 수도 있다.
    return [block_cnt,rainbow_cnt,blocks+rainbows]

def gravity():
    for j in range(n): #열
        for i in range(1,n):
            if board[i][j] == -2:
                for k in range(i-1,-1,-1):
                    if board[k][j] == -1: 
                        board[k+1][j] = -2
                        break
                    board[k+1][j] = board[k][j]
                else:
                    board[0][j] = -2
    return

def rotate():
    tmp = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            tmp[i][j] = board[j][n-1-i]
    for i in range(n):
        for j in range(n):
            board[i][j] = tmp[i][j]
    return
if __name__=='__main__':
    n, m = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    answer = 0
    while True:
        visited = [[0 for _ in range(n)] for _ in range(n)]
        blocks = []
        for i in range(n):
            for j in range(n):
                if board[i][j] > 0 and visited[i][j] ==0:
                    info = bfs(i,j)
                    if info[0] >=2:
                        blocks.append(info)
        blocks.sort(reverse=True)
        if len(blocks)==0:break
        answer += blocks[0][0]**2
        for x, y in blocks[0][2]:
            board[x][y] = -2
        # for i in range(n):
        gravity()
        rotate()
        gravity()
    print(answer)