[백준 14500. 테트로미노]

문제

폴리오미노란 크기가 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)

DFS, 백트래킹 - python 180ms

찾아본 결과 배열에서 해당 위치에서 거리 3까지만 DFS하면서 최댓값을 찾는 방법이 있었다.
탐색 도중 남은 칸이 모두 배열의 최댓값이라도 최대합보다 작다면 탐색을 중단한다.
배열의 최댓값은 max(map(max, arr)를 통해 구하였다.

하지만 그렇게하면 ㅗ모양의 테트로미노를 완성할 수 없는 문제가 있다.
이를 보완하기 위해 두번째 칸에 도착했을 경우 다음 칸을 방문 처리 및 값을 더하고,
다음 칸 좌표로 재귀호출이 아닌 현재 칸에서 거리만 추가하고 재귀호출 하는것이 포인트다.
그렇게 되면 두번째 칸 기준으로 아직 방문하지 않은 다른 방향으로 진행할 수 있다!

1. 처음 위치 방문 처리 및 값 추가
   

2. DFS로 방문하지 않은 칸으로 이동
   

3. idx 1일 때 다음 칸 방문처리 후 제자리에서 idx만 늘린 후 재귀 호출
   

4. 다른 방향으로 이동
   

5. 깊이 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)