[BOJ] 14500. 테트리미노(python)

📌문제

💪아이디어

1. 블록 모양만들기
   분홍색 블록을 제외한 모든 블록들은 한붓그리기가 가능하기때문에 분홍색 블록만 따로 처리해 주면 된다.
   
   • 분홍색 블록: 두번째 블록에서 상하좌우그리고 다시 두번째 블록으로 돌아오기
     
2. 백트래킹
   현재 가장 큰 합(answer)보다 현재 블록모양에 적힌 수의 합 + 남은 블럭 수만큼 종이에 쓰여 있는 수 중 가장 큰값 이 작다면 그 블럭은 검사할 필요가 없다.
   

🥂코드

import sys; input = sys.stdin.readline

dy = (-1,0,1,0)
dx = (0,1,0,-1)
answer = 0
max_val = 0

def dfs(y,x,block,total):
    global answer
    if answer >= total + max_val*(4-block): return
    if block == 4:
        answer = max(answer,total)
        return

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if 0<=ny<n and 0<=nx<m and not visited[ny][nx]:
            if block == 2:
                visited[ny][nx]=True
                dfs(y,x,block+1,total + board[ny][nx])
                visited[ny][nx]=False
            visited[ny][nx] = True
            dfs(ny,nx,block+1,total + board[ny][nx])
            visited[ny][nx] = False

n, m = map(int,input().split())
visited = [[False for _ in range(m)] for _ in range(n)]
board = []
for _ in range(n):
    board.append(list(map(int,input().split())))
    max_val = max(max_val,max(board[-1]))

for i in range(n):
    for j in range(m):
        visited[i][j]=True
        dfs(i,j,1,board[i][j])
        visited[i][j]=False
print(answer)