[백준] 14500 테트로미노 with Python

📌 BOJ 14500 테트로미노

💡 조건

1. 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

2. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 해야한다.

3. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

4. 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

5. N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다.
   입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

6. S의 문제

🖥 소스 코드

from sys import stdin

tetro = {
    # ㅁ
    0: [[(0, 0), (0, 1), (1, 0), (1, 1)]],
    # ㄱ,ㄴ
    1: [[(0, 0), (0, 1), (0, 2), (-1, 0)], [(0, 0), (0, 1), (0, 2), (1, 0)], [(0, 0), (0, 1), (0, 2), (1, 2)],
        [(0, 0), (0, 1), (0, 2), (-1, 2)],
        [(0, 0), (-1, 0), (-2, 0), (0, 1)], [(0, 0), (-1, 0), (-2, 0), (0, -1)], [(0, 0), (1, 0), (2, 0), (0, -1)],
        [(0, 0), (1, 0), (2, 0), (0, 1)]],
    # ㅡ, ㅣ
    2: [[(0, 0), (0, 1), (0, 2), (0, 3)], [(0, 0), (1, 0), (2, 0), (3, 0)]],
    # ㅗ, ㅓ
    3: [[(0, 0), (1, -1), (1, 0), (1, 1)], [(0, 0), (-1, -1), (-1, 0), (-1, 1)],
        [(0, 0), (0, 1), (-1, 1), (1, 1)], [(0, 0), (0, -1), (-1, -1), (1, -1)]],
    # ㄹ - =
    4: [[(0, 0), (1, 0), (1, 1), (2, 1)], [(0, 0), (0, 1), (-1, 1), (-1, 2)],
        [(0, 0), (1, 0), (1, -1), (2, -1)], [(0, 0), (0, 1), (1, 1), (1, 2)]]
}


n, m = map(int, stdin.readline().split())
board = []
for _ in range(n):
    board.append(list(map(int, stdin.readline().split())))


def get_value(x, y, blocks):
    global res
    for block in blocks:
        value = 0
        for i, j in block:
            nx, ny = i + x, j + y
            if -1 < nx < n and -1 < ny < m:
                value += board[nx][ny]
            else:
                break

        res = max(res, value)


res = -int(1e9)
for x in range(5):
    blocks = tetro[x]
    for i in range(n):
        for j in range(m):
            get_value(i, j, blocks)

print(res)

🔖 예제 및 실행결과

예제

5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

실행결과

19

⌨️ 문제 풀이

1. 테트로미노가 될 수 있는 모든 경우의 좌표를 tetro 라는 딕셔너리에 저장한다.

2. 종이의 크기와 종이에 써있는 숫자를 입력받아 각 변수 및 리스트에 저장한다.

3. 각 테트로미노가 위치할 수 있는 모양에 대해서 순회하면서, 각 좌표에서 놓을 수 있는 테트로미노 모양이 가질 수 있는 값 중 최댓값을 구한다.
   테트로미노의 좌표는 tetro 라는 변수에서 이미 가지고 있기 때문에, 기준이 되는 좌표 (i, j)에서 놓을 수 있는지 없는지도 구분할 수 있다.
   res 라는 변수가 최종적으로 답을 출력할 변수, value 가 좌표 (i, j) 의 위치에서 놓을 수 있는 테트로미노 모양에서의 값을 의미한다.

4. 각 테트로미노, 좌표값을 순회하고 갱신한 값 중 최댓값을 가지고 있는 res 를 출력한다.

💾 느낀점

1. 테트로미노 모양을 일일히 좌표로 정해두고 풀어야한다고 생각하지 못했다.
2. (1)번과 같은 생각을 해야하는 문제가 아닌, 시작점부터 bfs로 테트로미노 모양을 계산해서 풀어야한다고 생각했다가 큰 코 다칠뻔했다.
3. 테트로미노 모양을 좌표로 정해두고 나서는 그리 어려운 문제가 아니었다.