폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
처음에는 가능한 테트로미노의 모든 경우의 수를 좌표로 리스트에 추가 후 완전탐색하는 방법으로 풀었다. python으로는 7348ms pypy는 332ms로 통과하긴 했지만 최적화가 필요할 것 같아 풀이를 찾아봤다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
# 모든 조각의 경우의 수
tetris = [[(0, 0), (0, 1), (0, 2), (0, 3)],
[(0, 0), (1, 0), (2, 0), (3, 0)],
[(0, 0), (1, 0), (0, 1), (1, 1)],
[(0, 0), (1, 0), (2, 0), (2, 1)],
[(0, 1), (1, 1), (2, 1), (2, 0)],
[(0, 0), (0, 1), (1, 1), (2, 1)],
[(0, 0), (0, 1), (1, 0), (2, 0)],
[(0, 0), (1, 0), (1, 1), (1, 2)],
[(0, 2), (1, 1), (1, 2), (1, 0)],
[(0, 0), (0, 1), (0, 2), (1, 2)],
[(0, 0), (1, 0), (0, 1), (0, 2)],
[(0, 0), (1, 0), (1, 1), (2, 1)],
[(0, 1), (1, 1), (1, 0), (2, 0)],
[(1, 0), (1, 1), (0, 1), (0, 2)],
[(0, 0), (0, 1), (1, 1), (1, 2)],
[(0, 1), (1, 0), (1, 1), (1, 2)],
[(0, 0), (0, 1), (0, 2), (1, 1)],
[(0, 0), (1, 0), (1, 1), (2, 0)],
[(0, 1), (1, 1), (1, 0), (2, 1)]]
mx_cnt = 0
for i in range(N):
for j in range(M):
# 각 칸마다 테트리스 종류별로 대입
for k in tetris:
# 종류마다 카운트 초기화
cnt = 0
for l in range(4):
nx = i + k[l][0]
ny = j + k[l][1]
if 0 <= nx < N and 0 <= ny < M:
cnt += arr[nx][ny]
# 배역 밖으로 나가면 종료
else:
break
# 4칸 모두 탐색 후에 최댓값 갱신
mx_cnt = max(mx_cnt, cnt)
print(mx_cnt)
찾아본 결과 배열에서 해당 위치에서 거리 3까지만 DFS하면서 최댓값을 찾는 방법이 있었다.
탐색 도중 남은 칸이 모두 배열의 최댓값이라도 최대합보다 작다면 탐색을 중단한다.
배열의 최댓값은 max(map(max, arr)
를 통해 구하였다.
하지만 그렇게하면 ㅗ모양의 테트로미노를 완성할 수 없는 문제가 있다.
이를 보완하기 위해 두번째 칸에 도착했을 경우 다음 칸을 방문 처리 및 값을 더하고,
다음 칸 좌표로 재귀호출이 아닌 현재 칸에서 거리만 추가하고 재귀호출 하는것이 포인트다.
그렇게 되면 두번째 칸 기준으로 아직 방문하지 않은 다른 방향으로 진행할 수 있다!
처음 위치 방문 처리 및 값 추가
DFS로 방문하지 않은 칸으로 이동
idx 1일 때 다음 칸 방문처리 후 제자리에서 idx만 늘린 후 재귀 호출
다른 방향으로 이동
깊이 3까지 왔으므로 합산한 값 반환
디버깅하면서 방문배열을 확인하면 쉽게 이해할 수 있다.
import sys
input = sys.stdin.readline
def DFS(r, c, idx, cnt):
global mx_cnt
# 남은 칸들이 배열의 최댓값이더라도 최댓값보다 작으면 탐색 종료
if mx_cnt >= cnt + max_val * (3 - idx):
return
# 깊이 3까지 왔다면 최댓값 갱신
if idx == 3:
mx_cnt = max(mx_cnt, cnt)
return
else:
for i in range(4):
nr = r + dx[i]
nc = c + dy[i]
if 0 <= nr < N and 0 <= nc < M:
if visit[nr][nc] == 0:
# ㅗ 모양 탐색
if idx == 1:
visit[nr][nc] = 1
DFS(r, c, idx + 1, cnt + arr[nr][nc])
visit[nr][nc] = 0
# 다른 모양 탐색
visit[nr][nc] = 1
DFS(nr, nc, idx + 1, cnt + arr[nr][nc])
visit[nr][nc] = 0
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visit = [([0] * M) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
mx_cnt = 0
# 배열 안의 값 중 최댓값
max_val = max(map(max, arr))
for r in range(N):
for c in range(M):
# 탐색 후 방문처리 해제
visit[r][c] = 1
DFS(r, c, 0, arr[r][c])
visit[r][c] = 0
print(mx_cnt)