[python] 백준 14500번: 테트로미노

문제

www.acmicpc.net/problem/14500

14500번: 테트로미노

테마

브루트포스

 

아이디어

 

테트로미노들은 기본모양에서 90도씩 회전, x/y축 반전(뒤집기) 등이 가능하다. 네모의 칸수는 총 4칸.

 

돌리고 뒤집고 돌리고 뒤집고 ...

 

[[0,0,0],

 [0,0,0],

 [0,0,0]]

 

3*3 이내의 좌표로 모든 테트로미노의 좌표가 표현 가능하다. 무식하지만 총 19개의 테트로미노 경우의 수를

'tetrominos' 배열에 저장해 활용했다. 

 

N*M 배열에서 각 i행j열 좌표를 시작점으로 하는 모든 테트로미노의 경우의 수들을 cal_sum() 함수로 테트로미노 좌표의

값의 합을 구하고 이를 기존의 max_sum(최댓값) 과 max() 함수를 통해 최댓값을 갱신해나간다.

만약 좌표 범위내를 벗어나는 테트로미노의 경우에는

cal_sum() 함수에서 바로 '-1' 을 리턴해 최댓값이 갱신되지도 않고 반복문을 계속 돌리지도 않게 한다.

 

 

시간복잡도

시간복잡도는 O(N*M) 이다.

가능한 최대연산횟수를 계산해보면 N=4,M=200 일 때

4*200*19 = 15200 가 된다. 이는 생각보다 훠우워어얼씬 크지 않은 수다.

시간복잡도는 O(N*M) 이지만 실질적으로 상수인 테트로미노의 경우의 수 19를 무시할만큼 N 의 범위가 크지는 않다.

 

코드

 

from sys import stdin
tetrominos = [([0, 0], [0, 1], [0, 2], [0, 3]),  # ----
              ([0, 0], [1, 0], [2, 0], [3, 0]),
              ([0, 0], [0, 1], [1, 1], [1, 0]),  # ㅁ
              # ㄴ 모양
              ([0, 0], [1, 0], [1, 1], [1, 2]),
              ([0, 0], [0, 1], [1, 0], [2, 0]),
              ([0, 0], [0, 1], [0, 2], [1, 2]),
              ([0, 1], [1, 1], [2, 1], [2, 0]),
              ([0, 0], [0, 1], [1, 1], [2, 1]),
              ([1, 0], [1, 1], [1, 2], [0, 2]),
              ([0, 0], [1, 0], [2, 0], [2, 1]),
              ([0, 0], [1, 0], [0, 1], [0, 2]),
              # 번개모양
              ([0, 0], [1, 0], [1, 1], [2, 1]),
              ([1, 0], [1, 1], [0, 1], [0, 2]),
              ([2, 0], [1, 0], [1, 1], [0, 1]),
              ([0, 0], [0, 1], [1, 1], [1, 2]),
              # ㅜ 모양
              ([0, 0], [0, 1], [1, 1], [0, 2]),
              ([1, 0], [0, 1], [1, 1], [2, 1]),
              ([1, 0], [1, 1], [1, 2], [0, 1]),
              ([0, 0], [1, 0], [1, 1], [2, 0])]
 
def cal_sum(r, c, t ):  # t: 해당 tetromino 의 좌표 모음
    summ = 0
    global N, M
    for dx, dy in t:
        nx = r + dx
        ny = c + dy
        if 0 <= nx < N and 0 <= ny < M:
            summ += board[nx][ny]
        else:
            return -1
    return summ
 
 
N, M = map(int, stdin.readline().split())
board = []
for n in range(N):
    board.append(list(map(int, stdin.readline().split(' '))))
ans = 0
max_sum = 0
for r in range(N):
    for c in range(M):
        for tetromino in tetrominos:
            max_sum = max(max_sum, cal_sum(r, c, tetromino))
 
# edge-case : 19 (테트로미노 경우의 수) * 4 * 200 = 15200번 연산.
print(max_sum)