[백준] 14500 테트로미노 (Python 파이썬)

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

14500번: 테트로미노

문제 설명

링크에서 알 수 있듯이,

좌표 크기 N x M을 입력받은 후에 각각의 좌표 칸 마다 숫자를 부여한다.

 

그리고 우리가 흔히 해봤던 테트리스 게임의 블록 모양들을 이 좌표 위에 올려놓게 되는데

블록이 위치하는 좌표의 숫자들의 합이 최대가 되는 값을 구하면 된다.

즉, 내가 ㅡ(일자 막대) 모양의 블록을 (0,0) (0,1), (0,2), (0,3) 좌표 위에 올려놓았다면

이 네 좌표의 숫자 값을 모두 더해 저장해놓은 후에 이러한 값들의 최댓값을 구하면 되는 것이다.

 

---

풀이 과정

이 문제는 브루트 포스(Brute-Force) 유형의 구현 문제이다.

즉 모든 칸에 대해 검사를 해보아야 한다.

문제에서 주어진 맵의 크기가 상대적으로 작기 때문에 (4 ≤ N, M ≤ 500)

모든 블록을 모든 칸에 대해 검사하는 방법으로 해결하였다.

 

1. 모든 블록 모양을 각각의 함수로 만든다.

2. 모든 좌표 칸 마다 각각의 함수들의 결과값을 구해 최댓값을 구한다.

 

이 방법 외에도, 모든 블록모양을 담을 수 있는 큰 크기의 2차원 배열을 선언하여

2차원 배열안에 0과 1로 블록 모양을 지정해주는 방식도 있다.

 

편한 방법으로 문제를 해결하면 될 것 같다.

 

코드는 다음과 같다.

n, m = map(int,input().split())
graph = []
ans = 0

def shape1(i, j): # ㅡ
    if j+3 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i][j+3]

def shape2(i, j): # ㅣ
    if i+3 >= n:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+3][j]

def shape3(i, j): # L모양
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j+1]

def shape4(i, j): # L모양 대칭
    if i+2 >= n or j-1 < 0:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+2][j] + graph[i+2][j-1]

def shape5(i, j): # L모양 시계방향 회전
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i-1][j] + graph[i-1][j+1] + graph[i-1][j+2]

def shape6(i, j): # L대칭 시계방향 회전
    if i+1 >= n or j+2 >=m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+1][j+2]

def shape7(i, j): # L 시계방향 회전x2
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i+2][j+1]

def shape8(i, j): # L대칭 시계방향 회전x2
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j] + graph[i+2][j]

def shape9(i, j): # L 시계방향 회전x3
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i-1][j+2]

def shape10(i, j): # L대칭 시계방향 회전x3
    if i+1 >= n or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i][j+2] + graph[i+1][j+2]

def shape11(i, j): # ㅁ모양
    if i+1 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j] + graph[i+1][j+1]

def shape12(i, j): # 번개모양
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j+1]

def shape13(i, j): # 번개모양 회전
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i-1][j+1] + graph[i-1][j+2]

def shape14(i, j): #번개모양 대칭
    if i+2 >= n or j-1 < 0:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j-1] + graph[i+2][j-1]

def shape15(i, j): #번개모양 대칭 회전
    if i+1 >= n or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i+1][j+2]

def shape16(i, j): #ㅗ모양
    if i-1 < 0 or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i-1][j+1] + graph[i][j+2]

def shape17(i, j): #ㅗ모양 회전
    if i+2 >= n or j+1 >= m:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j+1] + graph[i+2][j]

def shape18(i, j): #ㅗ모양 회전x2
    if i+1 >= n or j+2 >= m:
        return 0
    return graph[i][j] + graph[i][j+1] + graph[i+1][j+1] + graph[i][j+2]

def shape19(i, j): #ㅗ모양 회전x3
    if i+2 >= n or j-1 < 0:
        return 0
    return graph[i][j] + graph[i+1][j] + graph[i+1][j-1] + graph[i+2][j]


for i in range(n):
    graph.append(list(map(int,input().split())))

for i in range(n):
    for j in range(m):
        ans = max(ans, shape1(i,j), shape2(i,j), shape3(i,j), shape4(i,j), shape5(i,j), shape6(i,j), shape7(i,j), shape8(i,j), shape9(i,j),
                  shape10(i,j), shape11(i,j), shape12(i,j), shape13(i,j), shape14(i,j), shape15(i,j), shape16(i,j), shape17(i,j), shape18(i,j), shape19(i,j))

print(ans)

 

 

 

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !