Baekjoon-14500-테트로미노
09 Oct 2022생각보다 시간제한 때문에 아주 까다로웠다…
생각해야 할 것은 두가지
- 가지치기: 해볼 필요도 없는 것 dfs에서 제외시키기
- DFS에서 global variable 사용하기: Max 함수를 남발했는데, 그게 꽤나 시간을 잡아먹는다. global 로 가능한 것은 global 처리 하자.
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
board = []
max_val = 0
for _ in range(N):
line = list(map(int,input().split()))
board.append(line)
max_val = max(*line,max_val)
visited = [[0]*M for _ in range(N)]
answer = 0
def dfs(idx,total,x,y):
global answer
if answer >= total + (3-idx) * max_val: # 가지치기(해볼 필요도 없는 것 무시해버리기)
return
if idx ==3:
answer = max(answer, total)
return
for dx,dy in [[0,1],[1,0],[0,-1],[-1,0]]:
nx,ny = x+dx, y+dy
if 0<=nx<N and 0<=ny<M and visited[nx][ny]==0:
if idx == 1:
visited[nx][ny] = 1
dfs(idx+1,total+board[nx][ny],x,y)
visited[nx][ny] = 0
visited[nx][ny] = 1
dfs(idx+1,total+board[nx][ny],nx,ny)
visited[nx][ny] = 0
for i in range(N):
for j in range(M):
visited[i][j] = 1
dfs(0,board[i][j],i,j)
visited[i][j] = 0
print(answer)