[BAEKJOON python] 21609_상어 중학교

상어 중학교
상어 중학교의 코딩 동아리에서 게임을 만들었다
이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있음
    블록은 검은색 블록, 무지개 블록, 일반 블록
    일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현
    검은색 블록은 -1
    무지개 블록은 0으로 표현
(i, j)는 격자의 i번 행, j번 열을 의미
|r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸

블록 그룹은 연결된 블록의 집합
일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다
검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다
그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다
블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록

오늘은 이 게임에 오토 플레이 기능을 만드려고 한다
오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복
1) 크기가 가장 큰 블록 그룹을 찾는다
    블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹
    그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을
    그 것도 여러개이면 열이 가장 큰 것을 찾는다
2) 1) 에서 찾은 블록 그룹의 모든 블록을 제거한다
    블록 그룹에 포함된 블록의 수를 B라고 했을 때, B^2점을 획득
3) 격자에 중력이 작용한다
4) 격자가 90도 반시계 방향으로 회전
5) 다시 격자에 중력이 작용
    격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동
    이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다

오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자

첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M
둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행
    각 행에 대한 정보는 1열부터 N열까지
    칸의 정보는 -1, 0, M이하

from collections import deque

# 격자 한 변의 크기 N, 색상의 개수 M
n, m = map(int, input().split())
# 격자의 칸에 들어있는 블록의 정보 (검은색 블록, 무지개 블록, 일반 블록은 M가지 색상)
board = [list(map(int, input().split())) for _ in range(n)]

# 반시계 방향
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def bfs(x, y, visited, b_num):
    queue = deque()
    queue.append((x, y))
    # 블록 정보
    c = board[x][y]
    # 일반 블록은 M가지 색상, 검은색 블록은 -1, 무지개 블록은 0
    # 방문처리 + 블록 그룹 번호 저장
    visited[x][y] = b_num
    size, r_n = 1, 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if board[nx][ny] == c and visited[nx][ny] == 0:
                    size += 1
                    visited[nx][ny] = b_num
                    queue.append((nx, ny))
                elif board[nx][ny] == 0 and not b_num in visited[nx][ny]:
                    size += 1
                    r_n += 1
                    visited[nx][ny].append(b_num)
                    queue.append((nx, ny))
    # 블록 그룹의 사이즈와, 블록 그룹 안에 있는 무지개 블록의 갯수
    return size, r_n

# 중력
def fall(x, y) :
    stop = False
    for i in range(x + 1, n) :
        nx = i
        if board[nx][y] != -2 :
            stop = True
            break
    if stop :
        board[nx-1][y] = board[x][y]
    else :
        board[nx][y] = board[x][y]
    # 블록을 제거한다. 제거 시 -2값으로 변경한다. 
    board[x][y] = -2

score = 0
while True:
    visited = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if board[i][j] == 0:
                visited[i][j] = []

    b_num, block = 1, []
    for i in range(n):
        for j in range(n):
            if board[i][j] > 0 and visited[i][j] == 0:
                # # 블록 그룹의 사이즈와, 블록 그룹 안에 있는 무지개 블록의 갯수
                size, r_n = bfs(i, j, visited, b_num)
                if size > 1:
                    # 그룹의 크기, 무지개블록의 갯수, 블록 기준 행, 열, 블록 번호
                    block.append([size, r_n, i, j, b_num])
                b_num += 1
    if len(block) == 0:
        break
    # 블록 그룹의 크기 -> 무지개 블록의 갯수 -> 블록 기준의 행 -> 열
    block.sort(key=lambda x:(-x[0], -x[1], -x[2], -x[3]))
    count = 0
    for i in range(n):
        for j in range(n):
            if board[i][j] > 0 and visited[i][j] == block[0][4]:
                count += 1
                board[i][j] = -2
            elif board[i][j] == 0 and block[0][4] in visited[i][j]:
                count += 1
                board[i][j] = -2

    score += (count*count)
    for i in range(n-2, -1, -1):
        for j in range(n):
            # 블록을 제거한다. 제거 시 -2값으로 변경한다. 
            if board[i][j] >= 0 and board[i+1][j] == -2:
                fall(i, j)

    board = list(map(list, zip(*board)))[::-1]

    for i in range(n-2, -1, -1):
        for j in range(n):
            # 블록을 제거한다. 제거 시 -2값으로 변경한다. 
            if board[i][j] >= 0 and board[i+1][j] == -2:
                fall(i, j)


print(score)

---

예제 입력

5 3
2 2 -1 3 1
3 3 2 0 -1
0 0 0 1 2
-1 3 1 3 2
0 3 2 2 1

예제 출력

77

 

 

 

이번껀.. 쫌.. 코드 해석이 어려웠다.

다시 도전할 것임.

https://developer-ellen.tistory.com/75