문제링크

21609 - 상어중학교

문제 설명

N*N크기의 격자 위에서 게임을 한다. 초기에는 모든 격자에 하나의 block이 있다. 블록의 종류는 검은색(-1), 무지개색(0), 일반(1~M)이다.

연결된 block의 집합을 블록 그룹이라고 한다. 적어도 1개의 일반 블록이 포함, 검은색 블록은 포함되면 안되고, 무지개색은 몇개가 포함되어도 상관이 없다. 최소 2개 이상의 블록으로 구성되어야 한다.
블록 그룹의 기준 block은 무지개 block이 아닌 것 중 행의 번호가 제일 작고, 열의 번호가 제일 작은 것이다.

오토플레이는 블록 그룹이 존재할 때까지 반복한다.

1. 크기가 제일 큰 block 그룹 찾기 ->$B^2$점을 획득한다
   : 같은 크기의 블록이 여러개면
   1. 포함된 무지개 블록이 제일 많은 것
   2. 기준 block의 행이 제일 큰 것
   3. 기준 block의 열이 제일 큰 것
   을 우선순위로 블록 그룹을 설정한다.
   

2. 격자에 중력을 작용한다
   : 검은색 블록 제외한 모든 block이 다른 블록 또는 경계를 만날때까지 행의 번호가 큰 칸으로 이동한다.

3. 격자를 반시계방향으로 90도 회전시킨다.

4. 격자에 중력을 작용한다.

오토플레이가 끝난 뒤 얻은 점수는?

문제 설명

테케는 다 맞았는데 제출할때 계속 틀렸습니다가 나왔다 ^_ㅜ 실제 시험이었으면 맞게 풀었다고 생각했을듯 ;;;;;;;;;;;;;;

입력받기

빈칸을 -2, 검은색을 -1, 무지개색을 0, 일반 블록을 1~m으로 뒀다.

N, M = map(int, input().split())
board = []
for _ in range(N):
    # -2:빈칸 -1:검은색 0:무지개색 1~:일반
    board.append(list(map(int, input().split())))

제일 큰 블록 그룹 찾기

격자를 (0,0)~(N-1,N-1)까지 순회하면서 일반 블록에 대해서 bfs를 적용하여 해당 일반 블록을 기준 블록으로 갖는 블록 그룹을 찾는다.

bfs는 다음과 같이 구현했다.

def findBlockGroup(i, j, visited):
    queue = deque()
    checked = [[False for _ in range(N)] for _ in range(N)]
    queue.append([i,j])
    checked[i][j] = True
    visited[i][j] = True
    block = [[i,j]]
    rainbow = 0

    while queue:
        x, y = queue.popleft()
        for d in range(4):
            nx, ny = x+dx[d], y+dy[d]
            if in_bound(nx, ny) and not checked[nx][ny] and (board[nx][ny] == board[i][j] or board[nx][ny] == 0):
                if board[nx][ny] == 0:
                    rainbow += 1
                elif board[nx][ny] > 0:
                    visited[nx][ny] = True
                checked[nx][ny] = True
                queue.append([nx,ny])
                block.append([nx,ny])
    return block, rainbow

여기서 주의해야될 점이 !!! bfs의 visited를 check하는 리스트외에 전체 block들에 대해 이미 다른 블록 그룹에 포함됐는지를 검사해야된다. (위 코드에서 visited 리스트) 이걸 검사하지 않으면 이미 블록 그룹에 포함된 블록을 기준 블록으로 삼아 다시 bfs를 돌고, 결론적으로 기준 블록이 바뀌어서 블록 그룹을 결정할때 우선순위를 제대로 계산할 수 없음 ^-ㅠ

    max_block = [[], -1, (-1, -1)] # [[블록좌표들], 무지개수블록, (기준블록좌표)]

    visited = [[False for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if board[i][j] > 0 and not visited[i][j]:
                block, rainbow = findBlockGroup(i,j, visited)
                if len(block) > 1:
                    # 포함된 블록이 2개 이상이면
                    if len(block) > len(max_block[0]):
                        max_block = [block, rainbow, i, j]
                    elif len(block) == len(max_block[0]):
                        # 무지개 블록이 제일 많은것
                        if rainbow > max_block[1]:
                            max_block = [block, rainbow, i, j]
                        elif rainbow == max_block[1]:
                            if i > max_block[2]:
                                # 행번호 큰거
                                max_block = [block, rainbow, i, j]
                            elif i == max_block[2]:
                                if j > max_block[3]:
                                    # 열번호 큰거
                                    max_block = [block, rainbow, i, j]

주어진 우선 순위대로 블록 그룹을 찾는다.

중력 적용하기

def move():
    for i in range(N-2, -1, -1):
        for j in range(N):
            if board[i][j] >= 0:
                x, y = i, j
                while True:
                    nx, ny = x+1, y
                    if in_bound(nx, ny) and board[nx][ny] == -2:
                        board[nx][ny] = board[x][y]
                        board[x][y] = -2
                        x, y = nx, ny
                    else:
                        break

중력 적용은 N-2번째 행부터 아래가 빈칸인 블록에 대해 한칸씩 내려준다.

반시계방향으로 90도 회전

def rotate_anticlockwise():
    new_board = copy.deepcopy(board)
    for i in range(N):
        for j in range(N):
            board[N-j-1][i] = new_board[i][j]

전체 코드

import sys
from collections import deque
import copy

input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

N, M = map(int, input().split())
board = []
for _ in range(N):
    # -2:빈칸 -1:검은색 0:무지개색 1~:일반
    board.append(list(map(int, input().split())))

def in_bound(x, y):
    if x in range(N) and y in range(N):
        return True
    return False

def findBlockGroup(i, j, visited):
    queue = deque()
    checked = [[False for _ in range(N)] for _ in range(N)]
    queue.append([i,j])
    checked[i][j] = True
    visited[i][j] = True
    block = [[i,j]]
    rainbow = 0

    while queue:
        x, y = queue.popleft()
        for d in range(4):
            nx, ny = x+dx[d], y+dy[d]
            if in_bound(nx, ny) and not checked[nx][ny] and (board[nx][ny] == board[i][j] or board[nx][ny] == 0):
                if board[nx][ny] == 0:
                    rainbow += 1
                elif board[nx][ny] > 0:
                    visited[nx][ny] = True
                checked[nx][ny] = True
                queue.append([nx,ny])
                block.append([nx,ny])
    return block, rainbow

def move():
    for i in range(N-2, -1, -1):
        for j in range(N):
            if board[i][j] >= 0:
                x, y = i, j
                while True:
                    nx, ny = x+1, y
                    if in_bound(nx, ny) and board[nx][ny] == -2:
                        board[nx][ny] = board[x][y]
                        board[x][y] = -2
                        x, y = nx, ny
                    else:
                        break
    
def rotate_anticlockwise():
    new_board = copy.deepcopy(board)
    for i in range(N):
        for j in range(N):
            board[N-j-1][i] = new_board[i][j]

answer = 0
while True:
    # 1. 제일 큰 블록 찾기
    max_block = [[], -1, (-1, -1)] # [[블록좌표들], 무지개수블록, (기준블록좌표)]

    visited = [[False for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if board[i][j] > 0 and not visited[i][j]:
                block, rainbow = findBlockGroup(i,j, visited)
                if len(block) > 1:
                    # 포함된 블록이 2개 이상이면
                    if len(block) > len(max_block[0]):
                        max_block = [block, rainbow, i, j]
                    elif len(block) == len(max_block[0]):
                        # 무지개 블록이 제일 많은것
                        if rainbow > max_block[1]:
                            max_block = [block, rainbow, i, j]
                        elif rainbow == max_block[1]:
                            if i > max_block[2]:
                                # 행번호 큰거
                                max_block = [block, rainbow, i, j]
                            elif i == max_block[2]:
                                if j > max_block[3]:
                                    # 열번호 큰거
                                    max_block = [block, rainbow, i, j]
    
    if max_block[0] == []:
        # 찾을 수 있는 블록 집합이 없으면
        break
    # 1.1 block 없애기
    for b in max_block[0]:
        board[b[0]][b[1]] = -2

    # 1.2 점수 획득
    answer += len(max_block[0])*len(max_block[0])
    
    # 2. 이동시키기
    move()

    # 3. 반시계방향으로 90도 회전
    rotate_anticlockwise()

    # 4. 이동시키기
    move()

print(answer)

소요시간

1시간 50분