폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. - 정사각형은 서로 겹치면 안 된다. - 도형은 모두 연결되어 있어야 한다.정사각형의 변끼리 연결되어 있어야 한다. - 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
설명
ㅗ모양을 제외한 네 개의 테트로미노는 DFS를 통해 회전, 대칭에 상관없이 접근할 수 있다. 즉 DFS를 통해 4개의 테트로미노 중 최댓값을 구하고 ㅗ모양 테트로미노는 브루트포스로 구해서 최댓값을 비교한다.
대칭, 회전이 가능하기 때문에 만들어질 수 있는 모든 모양에 접근하기 위해서는 방문 표시를 하면 안 되며 점을 모두 찍기 전으로 돌아갈 수 있어야한다. 즉 백트래킹을 써야한다. 이 때문에 BFS로는 구현할 수 없다.
DFS를 통해 깊이를 하나씩 늘려가며 탐색하는데 만약 깊이가 4를 넘으면 탐색을 종료하고 지나온 4개의 점의 합을 구하여 최댓값과 비교한다.
ㅗ모양에 대해 만들어질 수 있는 4개의 ㅗ에 대해 모든 경우를 구하고 최댓값과 비교한다.
코드
#14500번 테트로미노
def DFS(count,sum_val,i,j) :
if count >= 4 :
global result
result = max(result,sum_val)
return
di = [0,1,0,-1]
dj = [1,0,-1,0]
for index in range(4) :
next_i = i+di[index]
next_j = j+dj[index]
if 0<= next_i <n and 0<= next_j <m :
if visit[next_i][next_j] == False :
visit[next_i][next_j] = True
DFS(count+1,sum_val+paper[next_i][next_j],next_i,next_j)
visit[next_i][next_j] = False
def another_shape(i,j) :
global result
di = [[-1,1,0],[-1,0,0],[0,-1,1],[0,0,1]]
dj = [[0,0,-1],[0,1,-1],[1,0,0],[1,-1,0]]
for ni in range(4):
sum_val = paper[i][j]
for nj in range(3) :
next_i = i+di[ni][nj]
next_j = j+dj[ni][nj]
if 0<=next_i<n and 0<=next_j<m:
sum_val += paper[next_i][next_j]
result = max(result,sum_val)
if __name__ == "__main__":
n,m = map(int,input().split())
visit = [[False]*m for _ in range(n)]
paper = []
result = 0
for i in range(n):
paper.append(list(map(int,input().split())))
for i in range(n) :
for j in range(m) :
visit[i][j]=True
DFS(1,paper[i][j],i,j)
visit[i][j]=False
another_shape(i,j)
print(result)
