BOJ 14500 · 테트로미노

알고리즘 분류 : 브루트 포스  

테트로미노를 N*M 종이 맵에 하나 두었을 때, 얻을 수 있는 합의 최대를 구해야 한다. 테트로미노란 정사각형 4개를 이어붙인 도형이다. 문제에 주어진 5개의 테트로미노는 각각 회전, 대칭이 가능하다. 회전, 대칭을 모두 고려하면, 서로 다른 모양의 도형을 총 19가지 만들 수 있다.

• 19가지의 도형을 모두 만든다.
• 각 도형에서 하나의 사각형을 중심으로 인덱스를 설정한다. (그림 참조)
• 각 도형 중에 하나를 맵에 두고 합을 구한다.
• 가장 큰 합이 정답이다.

---

C++ 소스코드

#include <cstdio>

int n, m, ans;
int a[500][500];
const int b[19][4][2] = {
    { {0,0}, {0,1}, {1,0}, {1,1} }, // ㅁ
    { {0,0}, {0,1}, {0,2}, {0,3} }, // ㅡ
    { {0,0}, {1,0}, {2,0}, {3,0} },
    { {0,0}, {0,1}, {0,2}, {1,0} }, // ㄴ
    { {0,2}, {1,0}, {1,1}, {1,2} },
    { {0,0}, {1,0}, {1,1}, {1,2} },
    { {0,0}, {0,1}, {0,2}, {1,2} },
    { {0,0}, {1,0}, {2,0}, {2,1} },
    { {0,0}, {0,1}, {1,1}, {2,1} },
    { {0,0}, {0,1}, {1,0}, {2,0} },
    { {0,1}, {1,1}, {2,0}, {2,1} },
    { {0,0}, {1,0}, {1,1}, {2,1} }, // Z
    { {0,1}, {1,0}, {1,1}, {2,0} },
    { {0,1}, {0,2}, {1,0}, {1,1} },
    { {0,0}, {0,1}, {1,1}, {1,2} },
    { {0,0}, {0,1}, {0,2}, {1,1} }, // ㅗ
    { {0,1}, {1,0}, {1,1}, {1,2} },
    { {0,1}, {1,0}, {1,1}, {2,1} },
    { {0,0}, {1,0}, {1,1}, {2,0} }
};

void tetromino(int x, int y) {
    for (int i=0; i<19; i++) {
        int res = 0;
        for (int j=0; j<4; j++) {
            int nx = x + b[i][j][0];
            int ny = y + b[i][j][1];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                res += a[nx][ny];
            }
        }
        if (ans < res) ans = res;
    }
}

void solve() {
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            tetromino(i, j);
        }
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    solve();
    return 0;
}

---

Python 3 소스코드

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [
    [(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)]
]

def tetromino(x, y):
    global ans
    for i in range(19):
        s = a[x][y]
        for j in range(3):
            try:
                nx = x+b[i][j][0]
                ny = y+b[i][j][1]
                s += a[nx][ny]
            except IndexError:
                continue
        ans = max(ans, s)

def solve():
    for i in range (n):
        for j in range(m):
            tetromino(i, j)

ans = 0
solve()
print(ans)

✓ 파이썬 코드에서는 모든 도형의 중심을 (0, 0)으로 두고 인덱스를 설정했다.

---

참고

• 백준 온라인 저지 : BOJ 14500