테트로미노

문제

크기가 N X M인 종이 위에 테트리미노를 하나 놓으려고 합니다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰인 수의 합을 최대로 하는 문제입니다.

제약조건

• 세로크기 N, 가로크기 M (4 <= N,M <= 500)
• 입력으로 주어지는 수는 1000을 넘지 않는 자연수

풀이

테트로미노의 가지수는 다음과 같습니다. (총 19개)

테트로미노를 모든 칸에 대입한다고 가정했을때 500 X 500 X 19 < 1억 이므로 브루트포스가 가능합니다.
먼저, 테트리미노를 좌표로 표현합니다. 그 다음 모든칸에 테트리미노를 위치시킨다. 테트리미노가 판을 벗어나는 경우가 존재합니다. 이 경우 유효하지 않으므로 계산하지 않습니다. 테트리미노가 유효한 위치에 존재할 경우 해당 테트리미노의 숫자들을 모두 더한뒤 결과값과 비교하여 결과값보다 큰 경우 결과값을 갱신합니다.

코드

'''
Created by jun on 21/05/24
'''
'''
테트리미노 개수
1번 - 2개 (1회전)
2번 - 1개
3번 - 8개 (3회전 / 1대칭)
4번 - 4개 (1회전 / 1대칭)
5번 - 4개 (3회전)

테트리미노의 개수는 총 19개.

500 * 500 * 19
25000 * 19 = 475000 < 1억 -> 브루트포스 가능
'''
import sys

#테트리미노의 위치를 좌표로 표현함.
tetrominos = [
    [(0, 0), (0, 1), (1, 0), (1, 1)],
    [(0, 0), (0, 1), (0, 2), (0, 3)],
    [(0, 0), (1, 0), (2, 0), (3, 0)],
    [(0, 0), (0, 1), (0, 2), (1, 0)],
    [(1, 0), (1, 1), (1, 2), (0, 2)],
    [(0, 0), (1, 0), (1, 1), (1, 2)],
    [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (1, 0), (2, 0), (2, 1)],
    [(2, 0), (2, 1), (1, 1), (0, 1)],
    [(0, 0), (0, 1), (1, 0), (2, 0)],
    [(0, 0), (0, 1), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (0, 2), (1, 1)],
    [(1, 0), (1, 1), (1, 2), (0, 1)],
    [(0, 0), (1, 0), (2, 0), (1, 1)],
    [(1, 0), (0, 1), (1, 1), (2, 1)],
    [(1, 0), (2, 0), (0, 1), (1, 1)],
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(1, 0), (0, 1), (1, 1), (0, 2)],
    [(0, 0), (0, 1), (1, 1), (1, 2)]
]

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

#테트리미노가 유효한 위치에 자리하는지 검사하는 함수
def is_valid(y: int, x: int) -> bool:
    return 0 <= y < N and 0 <= x < M


#테트리미노를 자리에 위치시키는 함수
def func(y: int, x: int) -> None:
    res = 0
    for tetromino in tetrominos:
        acc = 0
        for dy, dx in tetromino:
            if not is_valid(y+dy, x+dx):
                break
            acc += board[y+dy][x+dx]
        else:
            res = max(res, acc)
    return res


result = -sys.maxsize
for y in range(N):
    for x in range(M):
        result = max(result, func(y, x))

print(result)

새로 알게된 사실

테트로미노의 좌표 구현