Baekjoon 14500번 테트로미노

문제

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

걸린 시간

02 : 04 : 10

풀이

Python3

import sys
input = sys.stdin.readline

def solve():
    m = 0
    for t in tetromino:
        xs, ys = t
        for i in range(0, len(xs)):
            dx, dy = xs[i], ys[i]
            for r in range(0, N):
                for c in range(0, M):
                    acc = 0
                    for j in range(0, 4):
                        nx = r + dx[j]
                        ny = c + dy[j]
                        if 0 <= nx < N and 0 <= ny < M:
                            acc += paper[nx][ny]
                    if m <= acc:
                        m = acc
    return m

if __name__ == "__main__":
    # N : 세로, M : 가로
    N, M = map(int, input().split())

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

    # x : 행, y : 열 
    lx = [[0, 0, 0, 0], [0, 1, 2, 3]]
    ly = [[0, 1, 2, 3], [0, 0, 0, 0]] 
    l = [lx, ly]

    ox = [[0, 0, 1, 1]]
    oy = [[0, 1, 0, 1]]
    o = [ox, oy]

    bx = [[0, 1, 2, 2], [0, 0, 0, 1], [0, 0, 1, 2], [0, 1, 1, 1]] 
    by = [[0, 0, 0, 1], [0, 1, 2, 0], [0, 1, 1, 1], [2, 0, 1, 2]] 
    b = [bx, by]

    dx = [[0, 1, 2, 2], [0, 0, 0, 1], [0, 0, 1, 2], [0, 1, 1, 1]]
    dy = [[1, 1, 0, 1], [0, 1, 2, 2], [0, 1, 0, 0], [0, 0, 1, 2]]
    d = [dx, dy]

    sx = [[0, 0, 1, 1], [0, 1, 1, 2]] 
    sy = [[1, 2, 0, 1], [0, 0, 1, 1]]
    s = [sx, sy]

    zx = [[0, 0, 1, 1], [0, 1, 1, 2]]
    zy = [[0, 1, 1, 2], [1, 0, 1, 0]]
    z = [zx, zy]

    Tx = [[0, 1, 1, 2], [0, 0, 0, 1], [0, 1, 1, 2], [0, 1, 1, 1]]
    Ty = [[0, 0, 1, 0], [0, 1, 2, 1], [1, 0, 1, 1], [1, 0, 1, 2]]
    T = [Tx, Ty]

    tetromino = [l, o, b, d, s, z, T]

    print(solve())

회전, 대칭시킨 테트로미노의 모든 모양을 종이 위에 올려보고 최대값을 찾는 브루트 포스 문제이다.

두 가지 모양 좌표를 나타내는데 실수가 있어 채점 중간에 틀렸습니다가 몇 번 출력됐다.

하드코딩이 아닌 dfs 로도 풀이할 수 있다고 한다.