[Python] [BOJ] 상어 중학교(21609)

💡 문제 해결

1. 배열 내에서 가장 긴 블록을 탐색
2. visited리스트를 생성하여 일반 블록을 중복 탐색하는 것을 방지
3. 배열을 완전탐색하며 일반블록일 경우 BFS로 이어진 블록을 탐색
4. 탐색하며 무지개 블록의 개수를 count해주고, 블록들의 좌표값을 한 개의 리스트에 저장
5. 탐색이 끝난 후 무지개 블록 개수와 기준 블록 좌표를 기준으로 블록 좌표정보 등 갱신
6. answer에 가장 길게 선택된 블록의 길이 제곱만큼의 값을 plus
7. 그렇게 선택된 좌표 정보들로 배열내 블록을 삭제
8. 마지막 행부터 비어있는 좌표일때 윗줄로 탐색을 시작하며 중력 기능 구현
9. 회전시킨 후 다시 중력
10. 가장 긴 블록의 길이가 2미만이 될 때까지 반복

📌 단순히 구현하는 문제였고, 조건이 많아 생각보단 까다로웠던 문제

🧾 문제 설명

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

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

오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 
오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.

크기가 가장 큰 블록 그룹을 찾는다. 
그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 
그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 
그 것도 여러개이면 열이 가장 큰 것을 찾는다.
1에서 찾은 블록 그룹의 모든 블록을 제거한다. 
블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
격자에 중력이 작용한다.
격자가 90도 반시계 방향으로 회전한다.
다시 격자에 중력이 작용한다.
격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 
이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.

문제보기

🖨 입출력

📝 풀이

import sys
from collections import deque


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

def search(tmp_arr, N):
    visited = [[False] * N for _ in range(N)]
    selected_blocks = []
    rainbow_cnt = 0
    start_block_x, start_block_y = -1, -1
    for i in range(N):
        for j in range(N):
            if tmp_arr[i][j] > 0 and visited[i][j] == False:
                tmp_selected_blocks = []
                tmp_rainbow_cnt = 0
                rainbows = []
                deq = deque([(i, j)])
                while deq:
                    x, y = deq.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if 0 <= nx < N and 0 <= ny < N:
                            if (tmp_arr[nx][ny] == 0 and (nx, ny) not in rainbows) or (tmp_arr[nx][ny] == tmp_arr[i][j] and visited[nx][ny] == False):
                                if tmp_arr[nx][ny] == 0:
                                    tmp_rainbow_cnt += 1
                                    rainbows.append((nx, ny))
                                else:
                                    visited[nx][ny] = True
                                deq.append((nx, ny))
                                tmp_selected_blocks.append((nx, ny))
                
                if len(tmp_selected_blocks) < len(selected_blocks):
                    continue
                elif len(tmp_selected_blocks) == len(selected_blocks):
                    if tmp_rainbow_cnt < rainbow_cnt:
                        continue
                    elif tmp_rainbow_cnt == rainbow_cnt:
                        if i < start_block_x:
                            continue
                        elif i == start_block_x:
                            if j < start_block_y:
                                continue
                rainbow_cnt = tmp_rainbow_cnt
                start_block_x, start_block_y = i, j
                selected_blocks = tmp_selected_blocks
    
    return selected_blocks, len(selected_blocks)


def delete_block(tmp_arr, blocks):
    for x, y in blocks:
        tmp_arr[x][y] = -5
    return tmp_arr


def gravity(tmp_arr):
    for j in range(N - 1, -1, -1):
        for i in range(N):
            if tmp_arr[j][i] == -5:
                move_x, move_y = i, j
                while 0 <= move_y - 1 and tmp_arr[move_y - 1][move_x] != -1:
                    move_y -= 1
                    if tmp_arr[move_y][move_x] >= 0: break
                if move_y != j:
                    tmp_arr[j][i] = tmp_arr[move_y][i]
                    tmp_arr[move_y][i] = -5
    return tmp_arr


def rotate(tmp_arr):
    for _ in range(3):
        tmp_arr = [list(elem) for elem in zip(*tmp_arr[::-1])]
    return tmp_arr
    
    
    
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

answer = 0
while True:
    selected_blocks, selected_length = search(arr, N)
    if selected_length < 2: break
    answer += selected_length ** 2
    arr = gravity(rotate(gravity(delete_block(arr, selected_blocks))))
    
print(answer)

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/21609