문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

입출력 예

풀이

! 연속된 4개의 칸을 택했을 때 어떻게 고르든 결국 테트리스 블럭 모양 중 하나임
1. depth가 4가 될때까지(4개의 칸을 선택할 때까지) 좌우상하를 탐색하여 방문하지 않은 칸을 방문
1. 1의 과정만으로는 ㅗ블럭의 경우, 탐색이 불가능함. 그래서 depth가 2일 때 1개를 선택하고, 선택하기 전의 위치에서 하나를 선택하게 되면 ㅗ이 되므로 따로 추가해줘야 됨

--> 이렇게 했을 때, 시간 초과가 났음. 중복의 경우까지 다 탐색하게 되어 케이스가 너무 많았음
--> 아래처럼 현재 합+2차원배열max값*(4-depth)을 해서 4칸의 합이 최대가 될 가능성이 없는 경우를 제외시켜서 탐색해줌

    temp=sum_
    for i in range(4-depth):
        temp+=maxValue

코드

import sys 
input = sys.stdin.readline
n,m=map(int,input().split())
graph=[list(map(int,input().split())) for _ in range(n)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
visited=[[0]*m for _ in range(n)]
maxValue=max(sum(graph,[]))
answer=0
def boundCheck(x,y):
    if(0<=x<n and 0<=y<m):
        return True
    return False
def search(x,y,depth,sum_):
    global answer
    temp=sum_
    for i in range(4-depth):
        temp+=maxValue
    if temp<answer:
        return
    if depth==4:
        answer=max(answer,sum_)
        return
    for i in range(4):
        dx=x+d[i][0]
        dy=y+d[i][1]
        if boundCheck(dx,dy) and visited[dx][dy]==0:
            if depth==2:
                visited[dx][dy]=1
                search(x,y,depth+1,sum_+graph[dx][dy])
                visited[dx][dy]=0
            visited[dx][dy]=1
            search(dx,dy,depth+1,sum_+graph[dx][dy])
            visited[dx][dy]=0
for i in range(n):
    for j in range(m):
        visited[i][j]=1
        search(i,j,1,graph[i][j])
        visited[i][j]=0
print(answer)