[백준] 14500 - 테트로미노

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

14500번: 테트로미노

Brute Force 문제

다른 분들 풀이를 보면 본래 의도는 블록을 하나씩 붙여가며 dfs 하는 문제로 보입니다.

(ㅜ 형태의 블록을 제외하고는 dfs, 해당 블록은 예외처리로 계산한다고 함..)

 

전 모든 블록의 회전, 반전 경우를 구하고 모든 위치에서 합을 계산했습니다...

python3로는 통과가 안되어 pypy2로 제출...

 

<pypy2 코드>

import sys
 
# 시계방향으로 90도 회전
def rotate_quad(block):
    first = []
    for i in range(len(block[0])):
        t = []
        for j in range(len(block)-1, -1, -1):
            t.append(block[j][i])
        first.append(t)
    return first
 
# 지정 횟수만큼 회전
def rotate(block, num):
    re = [block]
    temp = block
    for _ in range(num):
        temp = rotate_quad(temp)
        re.append(temp)
    return re
 
# 대칭
def inverse(block):
    re = []
    for l in block:
        re.append(list(reversed(l)))
    return re
 
# 기본 블록 형태. 백준 site 참고
blocks = [
    [[1, 1, 1, 1]],
    [[1, 1], [1, 1]],
    [[1, 0, 0], [1, 1, 1]],
    [[1, 1, 0], [0, 1, 1]],
    [[1, 1, 1], [0, 1, 0]]
]
# 반전, 회전시 동일한 블록 제외 위해 아래의 두 리스트를 설정
# 순서대로 반전 여부
inverses = [False, False, True, True, False]
# 순서대로 회전 횟수
rotates = [1, 0, 3, 1, 3]
 
lines = sys.stdin.readlines()
n, m = tuple(map(int, lines[0].split()))
paper = [list(map(int, line.split())) for line in lines[1:]]
 
re = 0
for block, inv, rot in zip(blocks, inverses, rotates):
    rot_inv = rotate(block, rot)
    if inv:
        rot_inv += rotate(inverse(block), rot)
 
    for case in rot_inv:
        # 블록을 위치시킬 수 있는 범위 내에서
        for i in range(n+1-len(case)):
            for j in range(m+1-len(case[0])):
                # 합을 계산
                tmp = 0
                for y in range(len(case)):
                    for x in range(len(case[0])):
                        tmp += case[y][x] * paper[i+y][j+x]
                re = max(re, tmp)
 
sys.stdout.write(str(re))