테트로미노 풀이

문제 링크: https://www.acmicpc.net/problem/14500

백준 알고리즘 기초 2/2 500에서 5번째 - 14500번 테트로미노를 풀어보았다.

 

풀이: https://velog.io/@jajubal/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-14500-%ED%85%8C%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8 를 참고했다.

 

C++

 

Python

def dfs(r,c,idx,total):
	global res
	if res>=total+maxs*(3-idx): return
	if idx==3:
		res=max(res,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 check[nr][nc]==0:
				if idx==1:
					check[nr][nc]=1
					dfs(r,c,idx+1,total+arr[nr][nc])
					check[nr][nc]=0
				check[nr][nc]=1
				dfs(nr,nc,idx+1,total+arr[nr][nc])
				check[nr][nc]=0

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for i in range(n)]
check=[[0]*m for i in range(n)]
dr=[-1,0,1,0]
dc=[0,1,0,-1]
res=0
maxs=max(map(max,arr))
for i in range(n):
	for j in range(m):
		check[i][j]=1
		dfs(i,j,0,arr[i][j])
		check[i][j]=0
print(res)

Java