[백준 21609번] 상어 중학교 (Python3)

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

def BFS(y,x,color):
  dq = deque()
  dq.append((y,x))
  result = set()
  rainbow = set()
  while dq:
    y,x = dq.popleft()
    if visited[y][x]:
      continue
    visited[y][x] = 1
    if matrix[y][x] == -2:
      rainbow.add((y,x))
    result.add((y,x))
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and N>x1>=0:
        if visited[y1][x1]:
          continue
        if matrix[y1][x1] == color or matrix[y1][x1] == -2:
          dq.append((y1,x1))
  rainbowcnt = len(rainbow)
  for y,x in rainbow:
    visited[y][x] = 0
  return result,rainbowcnt

def largegroup():
  maxresult,maxrainbowcnt = set(),0
  for i in range(N):
    for j in range(N):
      if not visited[i][j] and matrix[i][j] > 0:
        result,rainbowcnt = BFS(i,j,matrix[i][j])
        if len(result)>len(maxresult) or (len(result)==len(maxresult) and rainbowcnt>=maxrainbowcnt):
          maxresult,maxrainbowcnt = result,rainbowcnt
  return maxresult

def ccw():
  newmatrix = [[0]*N for i in range(N)]
  for i in range(N):
    for j in range(N):
      newmatrix[N-j-1][i] = matrix[i][j]
  return newmatrix

def down(y,x):
  v = matrix[y][x]
  matrix[y][x] = 0
  while True:
    if y+1==N or matrix[y+1][x]:
      break
    y += 1
  matrix[y][x] = v

def gravity():
  for x in range(N):
    for y in reversed(range(N)):
      if matrix[y][x] and matrix[y][x] != -1:
        down(y,x)      

N,M = map(int,input().split())
matrix = []
for i in range(N):
  matrix.append([*map(lambda x:-2 if not x else x,map(int,input().split()))])

result = 0
while True:
  visited = [[0]*N for i in range(N)]
  largest = largegroup()
  if len(largest) < 2:
    break
  result += len(largest)**2
  for y,x in largest:
    matrix[y][x] = 0
  gravity()
  matrix = ccw()
  gravity()

print(result)

 

딱히 어려울건 하나도 없는 문제인데 작성해야하는 코드양이 무지막지하게 긴 문제이다.

 

풀이방법은 지문에서 다 제시해주기 때문에 그냥 지문 그대로 차근차근 작성하면 된다. 이때 주의할 점 몇가지만 소개하면

1. 블록의 길이가 2 이상이어야 한다는 점.

2. 블록의 크기가 같고 무지개블록의 개수가 같은 경우 "행과 열이 큰 것을 골라야한다는 점"

 

을 주의해야 한다.

 

이외 나머지는 그냥 지문에서 시키는대로 하면 된다.

 

 

오늘의 교훈) 그냥 무지성 구현은 재미가 없는것 같다.