알고리즘 스터디 - 백준 14500번 : 테트로미노

문제 해석

• 폴리오미노는 정사각형을 여러 개 이어서 붙인 도형
• 정사각형은 겹칠수 없고 모두 변끼리 연결되어 있음
• 정사각형 4개를 이어붙인 폴리오미노 = 테트로미노
• 아름이는 NxM 종이 위에 테트로미노를 하나 놓았을 때 각 놓인 칸에는 정수가 있음

목적 : 테트로미노 하나를 놓아 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 함

어떤 알고리즘을 사용할까?

구현 문제이고 사각형의 크기가 크지 않기 때문에 한번 브루트 포스로 풀어보도록 하겠다. 하나의 좌표를 기준으로 가능한 모든 테트로미노를 시도하는 것이다.

1. 정사각형 (i, j) -> (i, j), (i+1, j), (i, j+1), (i+1, j+1)
2. 긴줄 사각형(세로) (i, j) -> (i, j), (i+1, j), (i+2, j), (i+3, j)
3. 긴줄 사각형(가로) (i, j) -> (i, j), (i, j+1), (i, j+2), (i, j+3)
   ... 이런 경우들을 다 종합해서 보면 아래와 같다.

[(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)],
[(0, 0), (0, 1), (0, 2), (-1, 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)],
[(0, 0), (0, 1), (1, 1), (2, 1)],
[(0, 0), (0, 1), (1, 0), (2, 0)],
[(0, 0), (1, 0), (2, 0), (2, -1)],
[(0, 0), (1, 0), (1, 1), (2, 1)],
[(0, 0), (0, 1), (1, 0), (-1, 1)],
[(0, 0), (0, 1), (1, 0), (1, -1)],
[(0, 0), (0, 1), (1, 1), (1, 2)],
[(0, 0), (0, 1), (0, 2), (1, 1)],
[(0, 0), (1, 0), (1, 1), (1, -1)],
[(0, 0), (1, 0), (2, 0), (1, -1)],
[(0, 0), (1, 0), (1, 1), (2, 0)]

알고리즘 코드

N, M = map(int, input().split())

descarte = []
for _ in range(N):
    position = list(map(int, input().split()))
    descarte.append(position)

score = []
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)],
    [(0, 0), (0, 1), (0, 2), (-1, 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)],
    [(0, 0), (0, 1), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (1, 0), (2, 0)],
    [(0, 0), (1, 0), (2, 0), (2, -1)],
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (1, 0), (-1, 1)],
    [(0, 0), (0, 1), (1, 0), (1, -1)],
    [(0, 0), (0, 1), (1, 1), (1, 2)],
    [(0, 0), (0, 1), (0, 2), (1, 1)],
    [(0, 0), (1, 0), (1, 1), (1, -1)],
    [(0, 0), (1, 0), (2, 0), (1, -1)],
    [(0, 0), (1, 0), (1, 1), (2, 0)]
]

for i in range(N):
    for j in range(M):
        for tetro in tetrominos:
            amount = 0
            for x, y in tetro:
                try:
                    amount += descarte[i+x][j+y]
                except IndexError:
                    break
            score.append(amount)

print(max(score))

• 메모리를 많이 쓰기 때문에 PyPy3로 풀게 되었다.