[백준] 상어 중학교 21609번 Python

문제

상어 중학교
오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.

연결된 블록의 집합에서

• 일반 블록을 적어도 하나 이상  포함
• 일반 블록의 색은 모두 같아야 함
• 검은색 블록은 포함되어선 안됨
• 블록의 수는 2개 이상
• 모두 인접하고 있어야 함

게임의 오토 플레이 기능을 만들기 위한 조건을 살펴보면

1. 블록의 크기 > 무지개 블록의 수 > 기준 블록의 행 > 기존 블록의 열 기준으로 큰 값을 가진 블록 그룹을 선택함
2. 위 1의 조건에서 찾은 블록 그룹의 모든 블록 제거, 블록 그룹의 포함된 블록의 수를 B 라고 할 때, B^2점을 획득함.
3. 격자에 중력이 작용한다.
4. 격자가 90도 반시계 방향으로 회전한다.
5. 다시 격자에 중력이 작용한다.

• 격자에 중력이 작용하면, 검은색 블록을 제외하고 모든 블록의 행의 번호가 큰 칸으로 이동한다. (down)
• 이동 시에 다른 블록이나 격자의 경계를 만나면 멈춘다.

 

문제 생각 & 풀이

문제를 이해한 후에 크기가 가장 큰 블록을 찾는 함수(1번), 블록을 제거해주는 함수(2번), 중력을 작용할 함수(3, 5번), 90도 반시계 회전시킬 함수(4번)로 나누어 알고리즘을 진행하는게 좋겠다고 생각이 들었다.

1. 크기가 가장 큰 블록을 큐를 활용하여 BFS 탐색

• 블록 그룹에 적어도 하나의 일반 블록 포함시키면서 완전 탐색 실행
• 완전 탐색을 하면서 무지개 블록과 일반 블록을 구분하여 발견 시에 그룹에 추가
• 정렬 기준에 맞도록 가장 큰 블록 그룹을 선택하여 반환
• 완전 탐색이 끝난 후에는 무지개 블록 방문은 다시 초기화
• 정렬 기준은 블록 그룹 크기 > 무지개 블록 수 > 기존 블록 행 > 기존 블록 열
• 람다를 활용한 정렬도 가능하지만 reverse=True 활용

 

2. 블록을 제거해주면서 점수 획득

• 제거된 블록은 -2로 표시
• 제거하면서 점수에 (해당그룹)^2 점 추가

 

3. 중력 작용시키기

• 블록들이 다른 블록이나 격자의 경계를 만날 때까지 아래로 이동
• 아래에서 위로 순회하면서 각 열에 대해서 순회할 때 검은색 블록일 때는 제외
• 현재 블록의 위치를 나타내는 변수 g를 활용
• 검은색 블록이 아니면서 블록판 이내의 범위이면서 빈 칸일 때만 아래로 이동
• 이동하고 난 후에 원래 자리는 빈 칸으로 표시해주고 
• g를 한 칸 아래로 이동시켜서 위치 업데이트

 

4. 90도 반시계 방향으로 회전시키기

• 90도 회전한 새 블록판을 만들어 줌
• 기존 블록판의 모든 요소를 순회하면서 각요소에 접근
• 기존 블록판의 행과 열을 새로운 위치로 매핑하여 90도 반시계 방향으로 회전
• 회전시킨 블록판으로 업데이트하여 사용해주기

 

위의 4가지 방법을 순서대로 생각하고 구현하면서 풀었다 !

 

ISSUE

크기가 가장 큰 블록을 찾는 함수에서 그룹을 찾는 과정을 잘 구현하지 못했었다. 따라서 블록 그룹을 제대로 탐색하고, 그룹의 정보를 반환하지 못하여서 rotate 함수를 호출할 때, 반환된 값을 block에 다시 할당하지 못하는 문제까지 발생했었다. 또한, 90도를 회전시키는 논리가 생각나지 않아 부끄럽지만 이 부분만 검색을 활용했다 ! ^^;

CODE

from collections import deque
import sys
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 가장 큰 블록 찾기
def find_big_block(i, j, block_number):
  q = deque()
  q.append((i, j)) # 시작점

  normal = [[i, j]] # 일반 블럭
  rainbow = [] # 무지개 블럭

  while q:
    x, y = q.popleft()
    for d in range(4):
      nx = x + dx[d]
      ny = y + dy[d]
      if 0 <= nx < N and 0 <= ny < N:
        # 범위 내 무지개 블록이면서 방문 안한 경우
        if block[nx][ny] == 0 and not visited[nx][ny]:
          visited[nx][ny] = 1
          q.append((nx, ny))
          rainbow.append([nx, ny]) # 무지개 리스트에 추가

        # 같은 색상의 일반 블록이면서 방문 안한 경우
        elif block[nx][ny] == block_number and not visited[nx][ny]:
          visited[nx][ny] = 1
          q.append((nx, ny))
          normal.append([nx, ny]) # 일반 리스트에 추가

  for x, y in rainbow: # 무지개 블록 방문 초기화
    visited[x][y] = 0

  # 블록 크기, 무지개블록 수, 블록 리스트
  return [len(normal+rainbow), len(rainbow), normal+rainbow]

# 블록 제거해주기
def remove(group):
  global score
  for x, y in group[2]:
    block[x][y] = -2 # 제거된 블록 = -2로 표시
  score += group[0] ** 2

# 중력 작용시키기
def gravity():
  for i in range(N-2, -1, -1): # 아래에서 위로
    for j in range(N):
      if block[i][j] != -1: # 검은색 블록이 아닐 때
        g = i
        while g+1 < N and block[g+1][j] == -2: # 빈 칸인 경우
          block[g+1][j] = block[g][j] # 아래로 이동
          block[g][j] = -2 # 원래 자리는 빈 칸으로 표시
          g += 1 # 한 칸 아래로 이동

# 90도 반시계 방향으로 회전
def rotate():
  global block
  new_block = [[0] * N for _ in range(N)] # 90도 돌렸을 때 블록판
  for i in range(N):
    for j in range(N):
      new_block[N-j-1][i] = block[i][j] # 90도 회전

  block = new_block # 새 블록판으로 업뎃

N, M = map(int, input().rstrip().split())
block = []
for _ in range(N):
  info = list(map(int, input().strip().split()))
  block.append(info)

score = 0
while True:
  visited = [[0] * N for _ in range(N)]
  group = [] # 그룹 리스트
  for i in range(N):
    for j in range(N):
      if block[i][j] >= 1 and not visited[i][j]:
        visited[i][j] = 1
        find_group = find_big_block(i, j, block[i][j]) # 블록 그룹 찾기
        if find_group[0] >= 2: # 2 이상일 때
          group.append(find_group) # 그룹 리스트에 추ㄱ

  group.sort(reverse=True) # 그룹 크기, 무지개 블록 수, 기준 블록 순으로 정렬

  if not group: # 그룹 없으면 종료
    break

  remove(group[0])
  gravity()
  rotate()
  gravity()

print(score)