문제

골드
테트리스 조각에 해당하는 공간만큼의 숫자를 더해서 최대값 구하기

아이디어

1. 좌표를 움직이면서 4칸 움직이면 멈추면 되겠다
   ➡ dfs를 쓰고 depth == 4 이면 값을 계산하자!

2. 컷엣지방식을 써서 가지치기하자 배열의 최대값을 구하기 maxv = max(map(max,arr))
   ➡ 현재의 총합(sumv) + arr의 최대값(maxv) * (3 - depth)번 곲한값 <= 현재의 최대값(result) 보다 작으면 어차피 최대값 갱신 불가 따라서 리턴

3. ㅗ,ㅜ 와 같은 방식은 계속 칸을 옮기면 만들어질 수 없다
   ➡ 블럭이 2개가 쌓였을 경우, dc,dr값을 더해주고, 다음 dfs를 진행할 때는 현재의 좌표에서 진행한다.

코드

import sys

sys.stdin = open('BOJ14500.txt')

N,M = map(int,sys.stdin.readline().split())
arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
dr=[0,0,1,-1]
dc=[1,-1,0,0]

result = 0
maxval = max(map(max, arr))

def dfs(cnt,sumV,r,c):
    global result
    if sumV + (3-cnt) * maxval <=result:
        return
    if cnt ==3:
        result = max(sumV,result)
        return
    else:
        for i in range(4):
            temp_r = r +dr[i]
            temp_c = c +dc[i]
            if 0<= temp_c < N and 0<=temp_r<M and not visit[temp_c][temp_r]:
                if cnt==1:
                    visit[temp_c][temp_r] = 1
                    dfs(cnt + 1, sumV + arr[temp_c][temp_r], r, c)
                    visit[temp_c][temp_r]=0

                visit[temp_c][temp_r]=1
                dfs(cnt+1,sumV+arr[temp_c][temp_r],temp_r,temp_c)
                visit[temp_c][temp_r]=0

visit = [[0] * M for _ in range(N)]
for c in range(N):
    for r in range(M):
        visit[c][r]=1
        dfs(0,arr[c][r],r,c)
        visit[c][r]=0

print(result)