[백준 14500번] 파이썬 - 테트로미노

http://www.acmicpc.net/problem/14500

 

 

# 조건

• 폴리오미노란 크기가 1 x 1인 정사각형을 여러 개 이어서 붙인 도형이며 아래 조건을 만족해야 된다.
  • 정사각형은 서로 겹치면 안됨
  • 도형은 모두 연결
  • 정사각형의 변끼리 연결되어 있어야 한다.
• 정사각형 4개를 이어 붙인 폴리오미노를 '테트로미노' 라고 하며, 아래 5가지가 있다.

 

 

• N x M 인 종이 위에 테트로미노 하나를 놓으려고 한다.
• 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하여라
• 회전이나 대칭 시켜도 된다.

 

# 접근 방법 및 Solution

• 각 도형을 돌렸을 때 포함 가능한 모양을 모두 구해준다.
• 이후 그 도형이 가지는 칸 수에 대해 조건을 달아주며 최댓값을 구한다.
• 모든 칸을 모든 도형에 대해 체크해주는 Brute Force 문제이다.
• 왼쪽 위부터 1번이라 하였을 때
  • 1 - 2개
  • 2 - 1개
  • 3 - 4개
  • 4 - 2개
  • 5 - 4개
  • 의 모양이 나온다.
• 대칭도 생각해준다면 3번 -> 8개 4번 -> 4개의 모양
• 제시되어 있는 모양을 시계방향으로 돌려주며 번호를 붙여주었다.
  • 3-2 번이란 오른쪽으로 90도 회전 시킨 것

import sys  
sys.stdin = open('input.txt')  
  
  
def check(i, j):  
    global result, N, M, arr  
    # 각 모양마다 범위 체크  
    # 1번 모양 - 세로 4칸, 가로 4칸    for i in range(N):  
        for j in range(M):  
            if i + 3 < N:  
                result = max(result, (arr[i][j] + arr[i+1][j] + arr[i+2][j] + arr[i+3][j]))  
            if j + 3 < M:  
                result = max(result, (arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i][j+3]))  
  
            # 2번 모양 - 세로 2 가로 2  
            if i + 1 < N and j+1 < M:  
                result = max(result, (arr[i][j] + arr[i][j+1] + arr[i+1][j] + arr[i+1][j+1]))  
  
            # 3-1번 모양 L자와 3-3번 모양 ㄱ자 길게, 3-3 대칭, 4-1  
            if i+2 < N and j+1 < M:  
                result = max(result, (arr[i][j] + arr[i+1][j] + arr[i+2][j] + arr[i+2][j+1]))  
                result = max(result, (arr[i][j] + arr[i][j+1] + arr[i+1][j+1] + arr[i+2][j+1]))  
                result = max(result, (arr[i][j] + arr[i][j+1] + arr[i+1][j] + arr[i+2][j]))  
                result = max(result, (arr[i][j] + arr[i+1][j] + arr[i+1][j+1] + arr[i+2][j+1]))  
            # 3-2번 모양 ㄱ 반대로, 3-2 대칭, 3-4 대칭, 4-2 대칭, 5-1  
            if i+1 < N and j+2 < M:  
                result = max(result, (arr[i][j] + arr[i+1][j] + arr[i][j+1] + arr[i][j+2]))  
                result = max(result, (arr[i][j] + arr[i+1][j] + arr[i+1][j+1] + arr[i+1][j+2]))  
                result = max(result, (arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+2]))  
                result = max(result, (arr[i][j] + arr[i][j + 1] + arr[i+1][j +1] + arr[i + 1][j + 2]))  
                result = max(result, (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1]))  
            # 3-4번 모양 ㄴ자 반대로, 4-2, 5-3  
            if 0 <= i-1 and j+2 < M:  
                result = max(result, (arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i-1][j+2]))  
                result = max(result, (arr[i][j] + arr[i][j+1] + arr[i-1][j+1] + arr[i-1][j + 2]))  
                result = max(result, (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j + 1]))  
            # 3-1 대칭, 4-1 대칭  
            if 0 <= i-2 and j+1 < M:  
                result = max(result, (arr[i][j] + arr[i][j+1] + arr[i-1][j+1] + arr[i-2][j+1]))  
                result = max(result, (arr[i][j] + arr[i-1][j] + arr[i - 1][j + 1] + arr[i - 2][j + 1]))  
            # 5-2, 5-4  
            if 0<= i-1 and i+1<N and j+1 <M:  
                result = max(result, (arr[i][j] + arr[i][j+1] + arr[i-1][j+1] + arr[i+1][j+1]))  
                result = max(result, (arr[i][j] + arr[i-1][j] + arr[i + 1][j] + arr[i][j + 1]))  
  
  
  
N, M = map(int, input().split())  
  
arr = [[*map(int, input().split())] for _ in range(N)]  
result = 0  
  
check(0,0)  
print(result)