[백준] 14500: 테트로미노 python 구현

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

 

풀이

냅다 19가지의 경우의 수를 만들었다.

이후 그냥 범위 안에 넣어 보면서 최대 값을 구하였음

CODE

import sys

n, m = map(int, input().split())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 첫 번째 칸을 기준으로 차지하는 dx, dy를 작성 
test_case = {
    1: [[0, 0, 0, 0], [0, 1, 2, 3]], # 파1
    2: [[0, 1, 2, 3], [0, 0, 0, 0]], # 파2
    3: [[0, 0, 1, 1], [0, 1, 1, 0]], # 노
    4: [[0, 1, 2, 2], [0, 0, 0, 1]], # 주1
    5: [[0, 0, 0, 1], [0, 1, 2, 0]], # 주2
    6: [[0, 0, 1, 2], [0, 1, 1, 1]], # 주3
    7: [[0, 0, 0, -1], [0, 1, 2, 2]], # 주4
    8: [[0, 1, 2, 2], [0, 0, 0, -1]], # 주5
    9: [[0, 1, 1, 1], [0, 0, 1, 2]], # 주6
    10: [[0, 0, 1, 2], [0, 1, 0, 0]], # 주7
    11: [[0, 0, 0, 1], [0, 1, 2, 2]], # 주8
    12: [[0, 1, 1, 2], [0, 0, 1, 1]], # 초1
    13: [[0, 0, -1, -1], [0, 1, 1, 2]], # 초2
    14: [[0, 1, 1, 2], [0, 0, -1, -1]], # 초3
    15: [[0, 0, 1, 1], [0, 1, 1, 2]], # 초4
    16: [[0, 0, 0, 1], [0, 1, 2, 1]], # 보1
    17: [[0, 0, -1, 1], [0, 1, 1, 1]], # 보2
    18: [[0, 0, 0, -1], [0, 1, 2, 1]], # 보3
    19: [[0, 1, 2, 1], [0, 0, 0, 1]] # 보4
}

max_sum = 0
for test in range(1, 20):
    tet_sum = 0
    for i in range(n):
        for j in range(m):

            dx, dy = test_case[test][0], test_case[test][1]

            tx_1, ty_1 = i + dx[0], j + dy[0]
            tx_2, ty_2 = i + dx[1], j + dy[1]
            tx_3, ty_3 = i + dx[2], j + dy[2]
            tx_4, ty_4 = i + dx[3], j + dy[3]

            if tx_1<0 or ty_1<0 or tx_1>(n-1) or ty_1>(m-1): continue
            if tx_2<0 or ty_2<0 or tx_2>(n-1) or ty_2>(m-1): continue
            if tx_3<0 or ty_3<0 or tx_3>(n-1) or ty_3>(m-1): continue
            if tx_4<0 or ty_4<0 or tx_4>(n-1) or ty_4>(m-1): continue

            tet_sum = paper[tx_1][ty_1] + paper[tx_2][ty_2] + \
                    paper[tx_3][ty_3] + paper[tx_4][ty_4]
            
            max_sum = max(tet_sum, max_sum)

print(max_sum)