[Python] 백준 <14500-테트로미노>

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

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

def dfs(x, y, cnt, total):
    global dap
    if cnt == 4:
        # 4개가 모이면 계산해서 답 초기화
        dap = max(dap, total)
        return
    # 4개 만들기
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 맵 내에 있고 방문하지 않았으면 추가 
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
            # 방문해서 체크하고 체크 완료하면 다시 미방문처리 (다음에도 또 방문해야 되기 때문에)
            visited[nx][ny] = True
            dfs(nx, ny, cnt + 1, total + t_map[nx][ny])
            visited[nx][ny] = False

def check_shape(x, y):
    global dap
    for shape in extra_shapes:
        total = 0
        boo = True  

        for ddx, ddy in shape:
            nx = x + ddx
            ny = y + ddy
            # 맵안에 없으면 넘어가기
            if not (0 <= nx < N and 0 <= ny < M):
                boo = False
                break  
            total += t_map[nx][ny]

        if boo:
            dap = max(dap, total)


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

visited = [[False]*M for _ in range(N)]
dap = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 'ㅗ' 모양을 구성하는 좌표
extra_shapes = [
    [(0, 0), (-1, 0), (0, -1), (0, 1)],  
    [(0, 0), (1, 0), (0, -1), (0, 1)],   
    [(0, 0), (-1, 0), (1, 0), (0, 1)],   
    [(0, 0), (-1, 0), (1, 0), (0, -1)]   
]

for i in range(N):
    for j in range(M):
        visited[i][j] = True
        dfs(i, j, 1, t_map[i][j])
        visited[i][j] = False
        check_shape(i, j)

# 'ㅗ'모양을 포함한 모든 패턴을 돌고 최대값 출력
print(dap)