[백준 21609번] 상어중학교(파이썬)

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

21609번: 상어 중학교

이 문제는

가장 큰 블록을 찾는 것이

가장 어려웠습니다.

저는 쌩쇼를 하다가

결국 서렌을 치고

솔루션을 보고나서야

아...내가 여태까지 뻘짓을 했다는 사실을 받아드렸죠.

 

저의 뻘짓을 먼저 나열하자면

 

1. 처음부터 큰 블록을 구한 뒤 비교하려고 했다

 

2. 우선 큰 블록을 구하는 알고리즘을 작성한 뒤에

이전의 큰 블록과 비교하는 식으로 구함

 

3. 문제의 조건에 맞춰서 큰 블록비교

 

이렇게 푸니깐 여러가지로 에로사항이 발생했습니다.

현재 가장 큰 블록입니다.

가장 큰 블록을 구할 때

저는 처음에 큰 블록을 구할 때

0과 다른 숫자를 넣는 것까지는 생각했습니다.

그런데 그 경우가 여러개라는 게 문제였습니다.

저렇게 빨간 경우에도

블록의 케이스가 있습니다.

그러면 저 케이스도 계산을 해야하는데

저는 '큰 거 먼저 고르자'라는 식으로 접근했기 때문에

저런 생각을 하지 못했습니다.

그러니 큰 거 업데이트해줄 때에도

계속 쓸데없이 길게

조건문을 넣었습니다.

(조건문이 쓸데없이 많아질 때 눈치를 챘었어야...)

대표적인 풀이법들은

'모든 블록을 구한 뒤에

가장 큰 걸 구하자'

라는 것이었습니다.

 

from collections import deque


# 인접 블록 찾기 -> 블록 크기, 무지개크기, 블록좌표 리턴
def bfs(x, y, color):
    q = deque()
    q.append([x, y])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    block_cnt, rainbow_cnt = 1, 0  # 블록개수, 무지개블록 개수
    blocks, rainbows = [[x, y]], []  # 블록좌표 넣을 리스트, 무지개좌표 넣을 리스트

    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 and not visited[nx][ny] and a[nx][ny] == color:
                visited[nx][ny] = 1
                q.append([nx, ny])
                block_cnt += 1
                blocks.append([nx, ny])

            # 범위 안이면서 방문 안한 무지개 블록인 경우
            elif 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and a[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append([nx, ny])
                block_cnt += 1
                rainbow_cnt += 1
                rainbows.append([nx, ny])

    # 무지개블록은 방문 다시 해제
    for x, y in rainbows:
        visited[x][y] = 0

    return [block_cnt, rainbow_cnt, blocks + rainbows]


# 블록 제거 함수
def remove(block):
    for x, y in block:
        a[x][y] = -2


# 중력 함수
def gravity(a):
    for i in range(N - 2, -1, -1):  # 밑에서 부터 체크
        for j in range(N):
            if a[i][j] > -1:  # -1이 아니면 아래로 다운
                r = i
                while True:
                    if 0 <= r + 1 < N and a[r + 1][j] == -2:  # 다음행이 인덱스 범위 안이면서 -2이면 아래로 다운
                        a[r + 1][j] = a[r][j]
                        a[r][j] = -2
                        r += 1
                    else:
                        break


# 반시계 회전 함수
def rot90(a):
    new_a = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            new_a[N - 1 - j][i] = a[i][j]
    return new_a


# 0. 메인코드
N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]

score = 0  # 점수

# 1. 오토플레이-> while {2. 크기 가장 큰 블록 찾기 3. 블록제거+점수더하기 4. 중력 5. 90회전 6. 중력}
while True:
    # 2. 크기 가장 큰 블록 찾기
    visited = [[0] * N for _ in range(N)]  # 방문체크
    blocks = []  # 가능한 블록 그룹들 넣을 리스트
    for i in range(N):
        for j in range(N):
            if a[i][j] > 0 and not visited[i][j]:  # 일반블록이면서 방문 안했으면
                visited[i][j] = 1  # 방문
                block_info = bfs(i, j, a[i][j])  # 인접한 블록 찾기
                # block_info = [블록크기, 무지개블록 개수, 블록좌표]
                if block_info[0] >= 2:
                    blocks.append(block_info)
    blocks.sort(reverse=True)

    # 3. 블록제거+점수더하기
    if not blocks:
        break
    remove(blocks[0][2])
    score += blocks[0][0] ** 2

    # 4. 중력
    gravity(a)

    # 5. 90회전
    a = rot90(a)

    # 6. 중력
    gravity(a)

print(score)

이 예시에서는 심플하게

모든 블록을 구한 다음에

큰 순서대로 정렬 후

가볍게 대소를 판단했습니다.

저렇게 대소판별을 할 수 있다니...

저건 미쳐몰랐네요.

 

뻘짓후에 솔루션을 보니 뭔가 허탈...ㅎㅎ

++++++

#백준 21609 상어중
from collections import deque
from copy import deepcopy

N,M=map(int,input().split())

graph=[list(map(int,input().split())) for _ in range(N)]

answer=0
dx=[1,-1,0,0]
dy=[0,0,1,-1]

def rotate():
    global graph
    temp=deepcopy(graph)
    for x in range(N):
        for y in range(N):
            temp[N-1-y][x]=graph[x][y]
    graph=deepcopy(temp)

def gravity():
    for y in range(N):
        for x in range(N-2,-1,-1):
            if graph[x][y]==-1 or graph[x][y]==-2:
                continue
            now=x
            while True:
                if now>=N-1:
                    break
                if graph[now+1][y]==-1:
                    break
                if not graph[now+1][y]==-2:
                    break
                now+=1
            graph[now][y],graph[x][y]=graph[x][y],graph[now][y]

def remove(block):
    for x,y in block:
        graph[x][y]=-2

def bfs(x,y):
    now=graph[x][y]
    queue=deque()
    queue.append([x,y])
    rain_cnt=0
    block_cnt=1
    blank=[]
    blank.append([x,y])
    rains=[]
    while queue:
        n_x,n_y=queue.popleft()
        for d in range(4):
            nx=n_x+dx[d]
            ny=n_y+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue
            if graph[nx][ny]==now and not visited[nx][ny]:
                visited[nx][ny]=True
                queue.append([nx,ny])
                blank.append([nx,ny])
                block_cnt+=1
            if graph[nx][ny]==0 and not visited[nx][ny]:
                visited[nx][ny]=True
                queue.append([nx,ny])
                rains.append([nx,ny])
                rain_cnt+=1
                block_cnt+=1

    for px,py in rains:
        visited[px][py]=False
    return [block_cnt,rain_cnt,blank+rains]


while True:
    visited=[[False]*N for _ in range(N)]

    #1. 블록 만들어주기
    #각각을 만들어주고 그중 가장 큰 블록
    #만들어주고 그중 가장 큰 걸 제거
    block=[]
    for x in range(N):
        for y in range(N):
            if graph[x][y]>0 and not visited[x][y]:
                visited[x][y]=True
                block_info=bfs(x,y)
                if block_info[0]>=2:
                    block.append(block_info)
    block.sort(reverse=True)

    if not block:
        break
    remove(block[0][2])
    answer+=block[0][0]**2
    #2 중력 적용
    gravity()
    #3 90도 회전
    rotate()
    #4 중력적용
    gravity()
print(answer)