[파이썬] [DFS] 백준 14500 테트로미노

문제

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

14500번: 테트로미노

코드

import sys
input=sys.stdin.readline

dx=[-1,1,0,0]
dy=[0,0,-1,1]

n,m=map(int, input().split())
array=[list(map(int, input().split())) for _ in range(n)]
visited=[[0]*m for _ in range(n)]
max_val =max(map(max,array)) #전체 중 가장 큰 값
result=0

def dfs(r,c,count,total):
    global result

	#가지치기
    # 현재의 dfs에서 남은 블록이 모두 최대라도 result를 못 넘기면 return
    if result>=total + max_val* (3-count):
        return

    if count==3:
        if result<total:
            result=total
        return

    for i in range(4):
        nx=r+dx[i]
        ny=c+dy[i]
        if 0<=nx<n and 0<=ny<m and visited[nx][ny]==0:
        	#ㅗ 부분 처리를 위해
            if count==1:
                visited[nx][ny] = 1
                dfs(r, c, count + 1,total+array[nx][ny])
                visited[nx][ny] = 0
            visited[nx][ny]=1
            dfs(nx,ny,count+1,total+array[nx][ny])
            visited[nx][ny] = 0

for i in range(n):
    for j in range(m):
        visited[i][j]=1
        dfs(i,j,0,array[i][j])
        visited[i][j]=0

print(result)