[백준 14500] 테트로미노

문제 보기

이 문제는 브루트 포스 문제이다. (DFS로도 풀 수 있다.)

위의 도형들을 회전, 대칭하여 만들 수 있는 총 블록들을 리스트에 저장하여, 종이의 각 칸에 방문할때마다 최대값을 찾는다.

다른 풀이를 보아하니, 보라색 테트로미노를 제외하고는 모두 DFS로 탐색 가능한 도형이다.

보라색을 제외한 모든 테트로미노들을 DFS로 탐색할 시, 모두 Depth가 3이다.

종이 위의 모든 칸을 순회하면서, DFS로 Depth가 3인 테트로미노와 보라색 테트로미노의 경우의 수 4가지를 비교해서 최대값을 구하면 된다.

import sys
 
n, m = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
blocks = [
    [(0, 1), (1, 0), (1, 1)],
    [(0, 1), (0, 2), (0, 3)],
    [(1, 0), (2, 0), (3, 0)],
    [(0, 1), (0, 2), (1, 0)],
    [(0, 1), (0, 2), (-1, 2)],
    [(1, 0), (1, 1), (1, 2)],
    [(0, 1), (0, 2), (1, 2)],
    [(1, 0), (2, 0), (2, 1)],
    [(0, 1), (1, 1), (2, 1)],
    [(0, 1), (1, 0), (2, 0)],
    [(1, 0), (2, 0), (2, -1)],
    [(1, 0), (1, 1), (2, 1)],
    [(0, 1), (1, 0), (-1, 1)],
    [(0, 1), (1, 0), (1, -1)],
    [(0, 1), (1, 1), (1, 2)],
    [(0, 1), (0, 2), (1, 1)],
    [(1, 0), (1, 1), (1, -1)],
    [(1, 0), (2, 0), (1, -1)],
    [(1, 0), (1, 1), (2, 0)]
]
 
 
answer = 0
for i in range(n):
    for j in range(m):
        for k in range(19):
            temp = board[i][j]
            for l in range(3):
                try:
                    new_r = i + blocks[k][l][0]
                    new_c = j + blocks[k][l][1]
                    temp += board[new_r][new_c]
                except IndexError:
                    continue
            answer = max(answer, temp)
print(answer)