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

백준 (BOJ) 14500
https://www.acmicpc.net/problem/14500

사용언어 : PYTHON

1.문제

2.풀이

브루트포스 알고리즘을 사용하는 문제이다.
시간제한은 2초인데 1억=1초의 룰에 대입했을때 2천8백만이 나오므로 브루트포스 알고리즘을 사용해도 된다.
499*499*19*6 = 28,386,114

회전 또는 대칭으로 만들 수 있는 모든 테트로미노를 1과 0의 배열로 만든다.

19개의 테트로미노들을 돌아가며 종이의 모든 배치 가능한 구역에 배치한다.

그리고 모든 배치중에서 최댓값을 찾는다.

이 문제를 통해서 연산이 복잡해 질 때는 함수를 사용하여 복잡한 연산들을 분할하면 좀 더 쉽게 구현할 수 있음을 알게되었다.

3.코드

import sys
import math
input = sys.stdin.readline

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

tetros=[
    [[1,1,1,1]],
    [[1],[1],[1],[1]],
    [[1,1],[1,1]],
    [[1,0],[1,0],[1,1]],
    [[1,1,1],[1,0,0]],
    [[1,1],[0,1],[0,1]],
    [[0,0,1],[1,1,1]],
    [[0,1],[0,1],[1,1]],
    [[1,1,1],[0,0,1]],
    [[1,1],[1,0],[1,0]],
    [[1,0,0],[1,1,1]],
    [[1,0],[1,1],[0,1]],
    [[0,1,1],[1,1,0]],
    [[0,1],[1,1],[1,0]],
    [[1,1,0],[0,1,1]],
    [[1,1,1],[0,1,0]],
    [[0,1],[1,1],[0,1]],
    [[0,1,0],[1,1,1]],
    [[1,0],[1,1],[1,0]]
]

def calc(t,i,j,paper): # 현재 tetro가 배치된 종이의 값을 계산하는 함수
    h,w = len(t),len(t[0])

    result=0

    for p in range(h):
        for q in range(w):
            result+=t[p][q]*paper[i+p][j+q]

    return result

def place(t,n,m,paper): # 전달받은 tetro를 종이의 모든 경우에 배치하고 최댓값을 리턴하는 함수
    h,w = len(t),len(t[0])
    result=0

    for i in range(n-h+1):
        for j in range(m-w+1):
            tmp=calc(t,i,j,paper) # 현재 tetro가 배치된 종이의 값을 계산하는 함수
            if tmp>result:
                result=tmp
    
    return result


max_tetro=0

for tetro in tetros: # 모든 tetro를 순회하면서 종이에 배치한다.
    tmp=place(tetro,N,M,paper) 
    if max_tetro < tmp:
        max_tetro=tmp

print(max_tetro)