백준 - 14500번(테트로미노,구현,브루트포스)

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

14500번: 테트로미노

구현은 아이디어만 떠올린다면 나머지는 코드를 적는 시간과의 싸움이다.

구현을 일종의 수준 높은 하드코딩이라고 부를 수도 있다. 물론 더 멋지고 이쁘게 푸는 방법이 있을 수 도 있다.

그러나 구현 문제는 단순하게 '구현' 하는 것이 목표다. 아이디어를 잘 떠올릴 수 있도록 똑똑하거나 다양한 구현 문제에 익숙해지는 게 좋다.

import sys

n,m = map(int,sys.stdin.readline().split())

arr = []
for _ in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))
ans = 0

def check(x,y):
    global ans

    #1번 가로
    if y+3 < m:
        tmp = arr[x][y] + arr[x][y+1] + arr[x][y+2] + arr[x][y+3]
        if tmp > ans:
            ans = tmp
    #1번 세로
    if x+3 < n:
        tmp = arr[x][y] + arr[x+1][y] + arr[x+2][y] + arr[x+3][y]
        if tmp > ans:
            ans = tmp
    #2번
    if x+1 < n and y+1 < m:
        tmp = arr[x][y] + arr[x+1][y] + arr[x][y+1] + arr[x+1][y+1]
        if tmp > ans:
            ans = tmp

    #3번 0도
    if x+2 < n and y+1 < m:
        tmp = arr[x][y] + arr[x+1][y] + arr[x+2][y] + arr[x+2][y+1]
        if tmp > ans:
            ans = tmp
    #3번 0도 대칭
    if x-2 >=0 and y+1 <m:
        tmp = arr[x][y] + arr[x][y+1] + arr[x-1][y+1] + arr[x-2][y+1]
        if tmp > ans:
            ans = tmp

    #3번 90도
    if x+1 < n and y+2 < m:
        tmp = arr[x][y] + arr[x][y+1] + arr[x][y+2] + arr[x+1][y]
        if tmp > ans:
            ans = tmp

    #3번 90도 대칭
    if x+1 < n and y+2 < m:
        tmp = arr[x][y] + arr[x][y+1] + arr[x][y+2] + arr[x+1][y+2]
        if tmp > ans:
            ans = tmp

    #3번 180도
    if x+2 < n and y+1 <m:
        tmp = arr[x][y] + arr[x][y+1] + arr[x+1][y+1] + arr[x+2][y+1]
        if tmp > ans:
            ans = tmp

    #3번 180도 대칭
    if x+2 < n and y+1 < m:
        tmp = arr[x][y] + arr[x+1][y] + arr[x+2][y] + arr[x][y+1]
        if tmp > ans:
            ans = tmp


    #3번 270도
    if x - 1 >= 0 and y + 2 < m:
        tmp = arr[x][y] + arr[x][y+1] + arr[x][y+2] + arr[x-1][y+2]
        if tmp > ans:
            ans = tmp

    #3번 270도 대칭
    if x+1 < n and y+2 < m:
        tmp = arr[x][y] + arr[x+1][y] + arr[x+1][y+1] + arr[x+1][y+2]
        if tmp > ans:
            ans = tmp

    #4번 0도
    if x+2 < n and y+1 < m:
        tmp = arr[x][y] + arr[x+1][y] + arr[x+1][y+1] + arr[x+2][y+1]
        if tmp > ans:
            ans = tmp

    #4번 0도 대칭
    if x + 2 < n and y-1 >=0:
        tmp = arr[x][y] + arr[x+1][y] + arr[x+1][y-1] + arr[x+2][y-1]
        if tmp > ans:
            ans = tmp

    #4번 90도
    if x-1 >= 0 and y + 2 < m:
        tmp = arr[x][y] + arr[x][y+1] + arr[x-1][y+1] + arr[x-1][y+2]
        if tmp > ans:
            ans = tmp

    #4번 90도 대칭
    if x + 1< n and y+2 <m:
        tmp = arr[x][y] + arr[x][y+1] + arr[x+1][y+1] + arr[x+1][y+2]
        if tmp > ans:
            ans = tmp

    #5번 0도
    if x+1 < n and y+2 < m:
        tmp = arr[x][y] + arr[x][y+1] + arr[x][y+2] + arr[x+1][y+1]
        if tmp > ans:
            ans = tmp

    # 5번 90도
    if x+2 < n and y-1 >=0:
        tmp = arr[x][y] + arr[x+1][y] + arr[x+2][y] + arr[x+1][y-1]
        if tmp > ans:
            ans = tmp

    #5번 180도
    if x-1 >=0 and y+2 < m:
        tmp = arr[x][y] + arr[x][y+1] + arr[x][y+2] + arr[x-1][y+1]
        if tmp > ans:
            ans = tmp
    #5번 270도
    if x+2 < n and y+1 <m:
        tmp = arr[x][y]+ arr[x+1][y] + arr[x+2][y] + arr[x+1][y+1]
        if tmp > ans:
            ans = tmp

for i in range(n):
    for j in range(m):
        check(i,j)

print(ans)

각 회전 했을 때의 테트로미노의 모양과 대칭했을 때의 모양도 고려해줘야 한다.

총 각 포인트당 19개의 경우의 수가 있다.

따라서 위처럼 브루트포스로 전부 구현해주면 n*m*19번의 연산으로 값을 찾을 수 있다.

주어진 배열을 전부 탐색하면서 조건에 해당하면 찾아보면 된다.

만약에 조건에 만족하는 값들의 합이 ans보다 크다면 ans 값을 교체해준다.

최종적으로 남는 ans값이 최댓값이다.