21609: 상어 중학교

풀이 시간

• 2h
• 구현 자체가 크게 어려운 문제는 아니었는데 1번 조건: "크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블룩 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그것도 여러개이면 열이 가장 큰 것을 찾는다."에서 맞는 블록 그룹을 찾는 게 처음 생각했던 방식대로는 잘 안돼서 한참 헤맸다. 이 부분은 아예 모든 groups를 구하고 내림차순 정렬을 통해 가장 앞의 group을 찾는 방식의 아이디어를 참고했다.

구현 방식

• 위에서 언급했지만, while문을 돌면서 매 turn마다 모든 group들을 구해주고, 해당 groups를 내림차순 정렬을 통해 가장 앞의 group을 찾는 방식으로 진행했다 (이렇게 해야 안정적으로 조건에 맞는 group이 찾아짐)

• 배열의 회전은 아래와 같이 python 내장함수를 이용함

# 반시계방향 90도 회전
board = list(reversed(list(map(list, zip(*board)))))

• bfs_find()
  -> 여기에서 주의할 점은, bfs 탐색을 진행하면서 rainbow_nodes를 기록해두고, 마지막에 rainbow_nodes를 visit 리스트에서 방문을 해제해줘야 한다는 점이다
  -> 반환 값은 순서대로 [그룹의 크기, 무지개블록의 개수, 그룹에 속한 모든 블록들의 좌표] 이다

• bfs_remove()
  -> input parameter로 그룹에 속한 모든 블록들의 좌표를 넘겨주고, 해당 좌표의 값들을 모두 -2로 바꿔줌
  -> 또한 그룹의 크기 * 2를 total_score에 더해줌

• gravity()
  -> 최상위 for문: 아래 row에서부터 위로 올라가면서 진행
  -> 검은색 블록(-1)과 비어있는 블록(-2)을 제외한 블록이 아래로 이동해야함
  -> while문을 돌면서 "다음 칸이 범위 안이고 비어있는 칸일 경우"에 swap 해줌 (그 외의 경우에 바로 break)

코드

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def gravity(board):
    for i in range(N-2, -1, -1):
        for j in range(N):
            if board[i][j] != -1 and board[i][j] != -2:
                r = i
                while True:
                    if 0 <= r+1 < N and board[r+1][j] == -2:
                        board[r+1][j] = board[r][j]; board[r][j] = -2
                        r += 1
                    else:
                        break

def bfs_find(x, y, standard_color):
    queue = deque([]); queue.append((x, y))
    visit[x][y] = True

    rainbow_nodes = []
    normal_nodes = [(x, y)]

    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] == standard_color and not visit[nx][ny]:
                    visit[nx][ny] = True
                    queue.append((nx, ny))
                    normal_nodes.append((nx, ny))
                elif board[nx][ny] == 0 and not visit[nx][ny]:
                    visit[nx][ny] = True
                    queue.append((nx, ny))
                    rainbow_nodes.append((nx, ny))

    for x, y in rainbow_nodes: #무지개블록은 방문을 다시 해제해줘야함!
        visit[x][y] = False

    return [len(normal_nodes + rainbow_nodes), len(rainbow_nodes), normal_nodes + rainbow_nodes]

def bfs_remove(group):
    global total_score
    total_score += group[0] ** 2

    for x, y in group[2]:
        board[x][y] = -2


N, M = map(int, sys.stdin.readline()[:-1].split())
board = []
for n in range(N):
    board.append(list(map(int, sys.stdin.readline()[:-1].split())))

total_score = 0
while True:
    # 크기가 가장 큰 블록 그룹 찾기
    groups = []
    visit = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if board[i][j] > 0 and not visit[i][j]: #일반블록부터 탐색을 시작해야함!
                group = bfs_find(i, j, board[i][j])
                if group[0] >= 2:
                    groups.append(group)
    groups.sort(reverse = True)

    if not groups: #블록 그룹 없음 -> 종료
        break

    # 찾은 블록 그룹의 모든 블록 제거 + 점수 획득
    bfs_remove(groups[0])

    # 중력 작용
    gravity(board)
                
    # 반시계방향 90도 회전
    board = list(reversed(list(map(list, zip(*board)))))

    # 다시 중력 작용
    gravity(board)

print(total_score)

결과