[코드트리] 파이썬 - 최적의 십자 모양 폭발

코드트리 - 최적의 십자 모양 폭발

 

# 접근 방법

• 완전 탐색을 활용한 시뮬레이션 문제이다.
• 0, 0부터 N-1, N-1까지 모든 폭탄을 터트린 후, 조건에 맞는지 검사해주면 된다.
• 항상 느끼는 것이지만, 모든 문제를 풀 때 각 기능을 함수로 나누는 것이 디버깅에도 유리하고 코드를 읽을 때도 잘 읽히는 것 같다.
• bomb함수
  • 폭탄을 터트리며 터진 곳을 저장해주었다.
  • 시작 위치는 height에 우선적 저장을 해주었는데, 1칸만 터지는 경우 세로로만 복사해주면 되기 때문이다.
• 시간을 가장 많이 소비한 곳은 폭탄을 터트린 후 격자에 중력을 작용시키는 부분이었다.
• gravity 함수
  • 가로로 터지는 부분은 최대 1칸이므로 터진 곳을 저장
  • 세로로 터지는 곳은 저장 후 정렬을 통하여 가장 위의 칸과 가장 아래 칸을 변수에 할당 시켜주었다.
  • 이 때, 터진 위치의 가장 윗 행이 0인 경우 continue를 해주었다.
• check 함수
  • 오른쪽과 아래만 확인하여 중복된 계산을 하지 않도록 해주었다.
• 함수를 크게 나누었지만 세부적으로 더 나눠주는 연습이 필요할 것 같다.
• 풀이 시간 40분

import sys  
input = sys.stdin.readline  
from copy import deepcopy  

# 폭탄 터트리기  
def bomb(temp, si, sj):  
    cnt = temp[si][sj]  
    temp[si][sj] = 0  
    # 가로의 경우 터진 곳 저장  
    # 세로의 경우 가장 윗 칸과 가장 아랫 칸 저장    
    width = []  
    height = [(si, sj)]  
    for d in range(4):  
        ni, nj = si, sj  
        now = cnt - 1  
        while now and 0<=ni+di[d]<N and 0<=nj+dj[d]<N:  
            ni += di[d]  
            nj += dj[d]  
            if d == 1 or d == 3:  
                width.append((ni, nj))  
            else:  
                height.append((ni, nj))  
            temp[ni][nj] = 0  
            now -= 1  

    gravity(temp, width, height)  

# 중력 떨어트리기  
def gravity(temp, width, height):  
    # 가장 윗칸인 경우 width는 무시하고 진행  
    if width and not width[0][0] == 0:  
        for wi, wj in width:  
            while wi - 1 >= 0:  
                temp[wi][wj] = temp[wi-1][wj]  
                temp[wi-1][wj] = 0  
                wi -= 1  
    # 가장 아랫 칸과 윗 칸을 변수에 할당 해주고  
    # 가장 윗 칸 -1 => 옮겨야 되는 칸이 범위 내이고 현재 칸이 폭탄이 터진 경우 계속 옮겨준다.    
    height.sort(reverse=True)  
    if not height[-1][0] == 0:  
        hi, hj, mi, mj = height[0][0], height[0][1], height[-1][0], height[-1][1]  
        mi, mj = mi-1, mj  
        while mi >= 0 and mi < N and temp[hi][hj] == 0:  
            temp[hi][hj] = temp[mi][mj]  
            temp[mi][mj] = 0  
            hi -= 1  
            mi -= 1  
    check(temp)  

def check(temp):  
    global result  
    cnt = 0  
    for ti in range(N):  
        for tj in range(N):  
            if temp[ti][tj]:  
                flag = temp[ti][tj]  
                # 아래와 오른쪽만 체크해준다.  
                for d in range(2):  
                    nti, ntj = ti + di[d], tj + dj[d]  
                    if 0<=nti<N and 0<=ntj<N:  
                        if flag == temp[nti][ntj]:  
                            cnt += 1  
    if cnt > result:  
        result = cnt  

N = int(input())  
arr = [list(map(int, input().split())) for _ in range(N)]  
result = 0  
di, dj = [1, 0, -1, 0], [0, 1, 0, -1]  

for i in range(N):  
    for j in range(N):  
        temp = deepcopy(arr)  
        bomb(temp, i, j)  
print(result)