벡준 14500 : 테트로미노 (파이썬)

1. 각각 도형을 회전시키면 이런 모양이 나온다.

2. 모든 도형의 범위를 확인해보면 다음과 같다.
   

3. 따라서 해당 범위만큼 dfs를 하면 된다.

정답코드

import sys; input = sys.stdin.readline

def dfs(r, c, depth, total):
    global ans
    if ans >= total + max_val * (3 - depth): #도형의 최대 갯수가 4개이므로 현재 + 최대값*3 보다 크면 return
        return
    if depth == 3: #dfs로 찾은 도형이 4개이면
        ans = max(ans, total)
        return
    else:
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < M and visit[nr][nc] == False:
                if depth == 1:
                    visit[nr][nc] = True
                    dfs(r, c, depth + 1, total + arr[nr][nc])
                    visit[nr][nc] = False
                visit[nr][nc] = True
                dfs(nr, nc, depth + 1, total + arr[nr][nc])
                visit[nr][nc] = False


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(N)]

visit = [([False] * M) for i in range(N)]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

ans = 0
max_val = max(map(max, arr)) # 2D어레이 중 가장 큰 row를 찾아서 그 row 중 다시 max값을 찾음

for r in range(N):
    for c in range(M):
        visit[r][c] = True
        dfs(r, c, 0, arr[r][c])
        visit[r][c] = False

print(ans)