악곱 == 악성곱슬

BruteForce, DFS

---

이 문제는 총 4개의 1x1 polyomino를 이용하여 총 4개로 이루어진 테트리미노를 이용하여 판에서 얻을 수 있는 최대값을 구현해보는 문제이다.

따라서 DFS(백트래킹)을 활용한 방법으로 구현하거나, 전부다 해보는 브루트 포스를 이용하여 해볼 수 있다.

브루트 포스에 대해서 알아보자면, 테트리미노의 총 가짓수는 19가지이다. 판의 최대 크기는 25만이다. 따라서 이를 곱하면 475만가지의 경우가 나오게 된다. 이는 전부 완전탐색 해도 괜찮은 크기의 연산량이다. 따라서 아래와 같이 구현할 수 있다.

구현

---

import sys

# 모든 도형 (회전 및 대칭한 모양 포함)
polys = [
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (-1, 1), (-1, 2)],
    [(0, 0), (-1, 0), (-1, 1), (-2, 1)],
    [(0, 0), (0, 1), (1, 1), (1, 2)],

    [(0, 0), (1, 0), (2, 0), (2, 1)],
    [(0, 0), (-1, 0), (-1, 1), (-1, 2)],
    [(0, 0), (0, 1), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (0, 2), (-1, 2)],
    [(0, 0), (0, 1), (-1, 1), (-2, 1)],
    [(0, 0), (1, 0), (1, 1), (1, 2)],
    [(0, 0), (-1, 0), (-2, 0), (-2, 1)],
    [(0, 0), (0, 1), (0, 2), (1, 2)],

    [(0, 0), (0, 1), (0, 2), (0, 3)],
    [(0, 0), (1, 0), (2, 0), (3, 0)],

    [(0, 0), (0, 1), (1, 0), (1, 1)],

    [(0, 0), (0, 1), (0, 2), (1, 1)],
    [(0, 0), (-1, 1), (0, 1), (1, 1)],
    [(0, 0), (1, -1), (1, 0), (1, 1)],
    [(0, 0), (1, 0), (2, 0), (1, 1)]
]

def get_max(n, m, poly):
    _max = 0
    for i in range(n):
        for j in range(m):
            _sum = 0
            for coord in poly:
                cx, cy = i + coord[0], j + coord[1]
                # 해당 좌표가 인덱스 범위 넘어가면
                if cx < 0 or cy < 0 or cx >= n or cy >= m:
                    _sum = 0
                    break
                # 안넘어가면
                _sum += graph[cx][cy]
            _max = max(_max, _sum)
    return _max

def solution(n, m):
    result = 0
    for poly in polys:
        result = max(result, get_max(n, m, poly))
    return result

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    graph = []
    for _ in range(N):
        graph.append(list(map(int, sys.stdin.readline().rstrip().split())))
    print(solution(N, M))