[PS] 백준 #14500. 테트로미노

문제 정보

• 난이도: 골드 V
• 문제 주소: https://www.acmicpc.net/problem/14500
• 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디

 

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

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

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

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

 

나의 풀이

설마 브루트포스로 이걸 구현할 수 있을까? 했는데 구현이 된다. 가능한 블록의 형태는 19가지고 모든 칸마다 확인을 한다 해도 최대 25000 * 19 * 4번의 연산이라 시간은 충분하다. 가능한 19가지 블록의 형태는 아래와 같다. (코드를 짜다보니 계속 실수가 나서 PPT로 만들어두었다.) 

이 블록들의 좌상단을 (0, 0)이라 두고 각 칸의 dx, dy가 얼마나 되는지를 blocks 벡터에 추가하였다. findMax 함수에서는 blocks 벡터와 블록 영역의 최대 width, height를 매개변수로 받는다. 이 함수는 모든 점마다 해당 블록이 삽입되었을 때 몇 점을 얻는지를 계산해서 리턴한다.

#include <bits/stdc++.h>
#define MAX 500

using namespace std;

int board[MAX][MAX]{};

int n, m;

// block: 블록 모양(왼쪽 위부터 인덱스로 셈) / bwidth: 블록의 너비 / bheight: 블록의 높이
int findMax(vector<pair<int,int>>& blocks, int bheight, int bwidth) {
    int ret = 0;
    for (int i = 0; i <= n - bheight; i++) {
        for (int j = 0; j <= m - bwidth; j++) {
            int tp = 0;
            for (pair<int, int> p : blocks) {
                tp += board[i + p.first][j + p.second];
            }
            ret = max(ret, tp);
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            cin >> board[i][j];

    int ans = 0;
    vector<pair<int, int>> blocks;

    // 1. 1*4
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(0, 2));
    blocks.push_back(make_pair(0, 3));
    ans = max(ans, findMax(blocks, 1, 4));

    // 2. 4*1
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(2, 0));
    blocks.push_back(make_pair(3, 0));
    ans = max(ans, findMax(blocks, 4, 1));

    // 3. 2*2
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(1, 0));
    ans = max(ans, findMax(blocks, 2, 2));

    // 4. 3 + 1 (기본 방향)
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(2, 0));
    blocks.push_back(make_pair(2, 1));
    ans = max(ans, findMax(blocks, 3, 2));

    // 5. 3 + 1 (90도 우회전)
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(0, 2));
    blocks.push_back(make_pair(1, 0));
    ans = max(ans, findMax(blocks, 2, 3));

    // 6. 3 + 1 (180도 우회전)
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(2, 1));
    ans = max(ans, findMax(blocks, 3, 2));

    // 7. 3 + 1 (270도 우회전)
    blocks.clear();
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(1, 2));
    blocks.push_back(make_pair(0, 2));
    ans = max(ans, findMax(blocks, 2, 3));

    // 8. 3 + 1 (기본 + 대칭)
    blocks.clear();
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(2, 1));
    blocks.push_back(make_pair(2, 0));
    ans = max(ans, findMax(blocks, 3, 2));

    // 9. 3 + 1 (90도 우회전 + 대칭)
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(0, 2));
    blocks.push_back(make_pair(1, 2));
    ans = max(ans, findMax(blocks, 2, 3));

    // 10. 3 + 1 (180도 우회전 + 대칭)
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(2, 0));
    ans = max(ans, findMax(blocks, 3, 2));

    // 11. 3 + 1 (270도 우회전 + 대칭)
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(1, 2));
    ans = max(ans, findMax(blocks, 2, 3));

    // 12. 1 + 2 + 1 (기본)
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(2, 1));
    ans = max(ans, findMax(blocks, 3, 2));

    // 13. 1 + 2 + 1 (90도 회전)
    blocks.clear();
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(0, 2));
    ans = max(ans, findMax(blocks, 2, 3));

    // 14. 1 + 2 + 1 (기본 + 대칭)
    blocks.clear();
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(2, 0));
    ans = max(ans, findMax(blocks, 3, 2));

    // 15. 1 + 2 + 1 (90도 회전 + 대칭)
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(1, 2));
    ans = max(ans, findMax(blocks, 2, 3));

    // 16. ㅜ 모양 (기본)
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(0, 2));
    blocks.push_back(make_pair(1, 1));
    ans = max(ans, findMax(blocks, 2, 3));

    // 17. ㅓ 모양 (왼쪽)
    blocks.clear();
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(2, 1));
    ans = max(ans, findMax(blocks, 3, 2));

    // 18. ㅗ 모양 (위쪽)
    blocks.clear();
    blocks.push_back(make_pair(0, 1));
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(1, 2));
    ans = max(ans, findMax(blocks, 3, 2));

    // 19. ㅏ 모양 (오른쪽)
    blocks.clear();
    blocks.push_back(make_pair(0, 0));
    blocks.push_back(make_pair(1, 0));
    blocks.push_back(make_pair(1, 1));
    blocks.push_back(make_pair(2, 0));
    ans = max(ans, findMax(blocks, 3, 2));
    
    cout << ans;
}

 

추가로 브루트 포스를 안쓰고 풀 수 있을까 고민해보니 BFS, DFS로 푸는 방식과 크루스칼 알고리즘이 떠올랐다. BFS, DFS는 각 정점으로부터 4칸씩 돌렸을때의 최댓값을 찾으면 되겠다고 생각했는데 이 경우 ㅗ, ㅜ, ㅓ, ㅏ 모양이 제대로 나오지 않을 것 같았다. 크루스칼 알고리즘은 각 점들 사이마다 엣지를 만들어 가중치를 두 정점의 합으로 두고, 기존 크루스칼과 다르게 가장 큰 순서부터 꺼내서 유니온 파인드로 노드의 개수가 4가 될때까지 연결하면 되지 않을까 생각했다. 하지만 이 방법은 당장 [예제 입력 3]부터 적용이 되지 않았다. 모든 엣지의 크기가 같기 때문에 이 경우 6이나 7 중에서 무엇이 나올지 확신할 수 없었다. 그래서 브루트포스 구현 연습겸 모든 블록을 하나하나 표현해서 구현하게 되었다.