상어 중학교 [백준 21609번]

문제

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

21609번: 상어 중학교

 

내 풀이

 

문제에서 말한 모든 조건을 다 구현하였다.

bfs를 사용하여 블록 그룹을 확인하였다.

그리고 크기가 가장 큰 블록 그룹을 찾을 때에는 블록 그룹의 좌표들을 리스트에 저장하여서 확인하였다.

지워야 하는 블록 그룹은 -2로 만들었다.

 

중력을 구할 때에는 카운트를 사용하였다.

-2(빈 곳) 일 때는 카운트를 세어서 -2가 연속으로 몇 칸 있는지 구하였다.

-1(검은 블록)일 때는 카운트를 0으로 초기화시켜주었다. 검은 블록은 이동하지 않기 때문이다.

일반 블록일 때는 카운트만큼 밑으로 내려주었다. 

 

list(map(int, zip(*board)))를 사용하여 2차원 배열을 시계 반대방향으로 회전시켰다.

 

from collections import deque

N, M = map(int, input().strip().split())
board = [list(map(int, input().strip().split())) for _ in range(N)]
dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]

def gravity(board):
    new_board = [[-2]*N for _ in range(N)]
    for j in range(N):
        cnt = 0
        for i in range(N - 1, -1, -1):
            if board[i][j] == -2:
                cnt += 1
            elif board[i][j] == -1:
                cnt = 0
                new_board[i][j] = -1
            else:
                new_board[i+cnt][j] = board[i][j]
    return new_board

def bfs(x, y, check):
    general_group, rainbow_group = [], []
    q = deque()
    check[x][y] = True
    q.append((x, y))
    general_group.append((x, y))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if not check[nx][ny] and (board[nx][ny] == m or board[nx][ny] == 0):
                    check[nx][ny] = True
                    q.append((nx, ny))
                    if board[nx][ny] == m:
                        general_group.append((nx, ny))
                    elif board[nx][ny] == 0:
                        rainbow_group.append((nx, ny))
    return general_group, rainbow_group

score = 0
while True:
    groups = []
    groups_info = []
    idx = 0
    # 블록이 제거된 곳 : -2
    for m in range(1, M + 1):
        # 일반블록 m과 무지개 블록 0으로 구성된 블록 그룹 찾기
        check = [[False] * N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                if board[i][j] == m and not check[i][j]:
                    general_group, rainbow_group = bfs(i, j, check)
                    if len(general_group + rainbow_group) < 2:
                        continue
                    base_block = sorted(general_group)[0]  # 기준 블록
                    groups.append(general_group + rainbow_group)
                    groups_info.append(
                        (idx, len(general_group + rainbow_group), len(rainbow_group), base_block[0], base_block[1]))
                    idx += 1
    if not groups:
        print(score)
        break
    groups_info.sort(key=lambda x: (-x[1], -x[2], -x[3], -x[4]))
    biggest_block = groups[groups_info[0][0]]
    score += len(biggest_block) ** 2
    for x, y in biggest_block:
        board[x][y] = -2
    board = gravity(board)[:]
    board = list(map(list, zip(*board)))[::-1]
    board = gravity(board)[:]

 

총평

다른건 어찌어찌 구현했는데, 중력을 구현하는 데에 많은 시간을 썼다.

검은색 블록은 중력의 영향을 받지 않기 때문에 이것을 고려하는 것이 너무 어려웠다.

너무 어려워서 머리에 쥐가 나려는 찰나 유튜브에서 na982님의 풀이를 보고 깨달았다. 아... 카운트...