BOJ 14500. 테트로미노

• 문제링크 : https://www.acmicpc.net/problem/14500

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

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
• 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

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

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

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

1. 문제해석

우선, 주어진 테트로미노를 회전, 대칭하여 만들 수 있는 테트로미노는 1+2+4+4+8=19로 총 19개이다.

그러면 한 개씩 종이 칸에 테트로미노를 하나씩 놓아보면서 합이 가장 큰 것을 구하기 위해서는 브루트 포스로 하나씩 다 맵핑해 보아야 한다. 아래와 같은 경우에 시간 복잡도는 가로가 N, 세로가 M이라고 하면 (N-3)x(M-3)이지만 N,M이 커지면 O(NxM)이 된다. 19개를 모두 해 보아야 하므로, 19xNxM이지만 19는 N과 M에 비해 매우 작기때문에 총 시간복잡도는 O(NxM)이다.

여기서 N과 M은 500을 넘지 않으므로, 충분한 시간안에 브루트 포스로 풀이가 가능하다.

---

2. 문제 풀이

19개의 각 테트로미노의 모양은 고정이므로 직접 다 입력해주는 방법으로 구현한다. 그리고 정수가 쓰여진 맵을 이차원 배열로 받아서, 범위를 넘지않도록 맵핑하고 반복하면서 최댓값을 찾는다.
각 테트로미노에 따라 범위 제한은 달라질 것이다. 위의 그림처럼 검은색 점 부분만 반복하면 된다고 생각할 수 있다.

#include <iostream>
using namespace std;

int map[1000][1000];

int main(){
    int N,M;
    cin >> N >> M;
    int answer=0;
    
    for(int i=0;i<N;++i){
        for(int j=0;j<M;++j){
            cin >> map[i][j];
        }
    }    
    for(int i=0;i<N;++i){ // type 1
        for(int j=0;j<M-3;++j){
            if(map[i][j]+map[i][j+1]+map[i][j+2]+map[i][j+3] > answer)
                answer=map[i][j]+map[i][j+1]+map[i][j+2]+map[i][j+3];
        }
    }
    for(int i=0;i<N-3;++i){
        for(int j=0;j<M;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i+3][j] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i+3][j];
        }
    }    
    for(int i=0;i<N-1;++i){ // type 2
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j]+map[i+1][j+1] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j]+map[i+1][j+1];
        }
    }
    
    for(int i=0;i<N-2;++i){ // type 3
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i+2][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i+1][j]+map[i][j+1]+map[i][j+2] > answer)
                answer=map[i][j]+map[i+1][j]+map[i][j+1]+map[i][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i+1][j]+map[i+1][j+1]+map[i+1][j+2]+map[i][j+2] > answer)
                answer=map[i+1][j]+map[i+1][j+1]+map[i+1][j+2]+map[i][j+2];
        }
    }
    for(int i=0;i<N-2;++i){ // type 3 - symmatric
        for(int j=0;j<M-1;++j){
            if(map[i][j+1]+map[i+1][j+1]+map[i+2][j+1]+map[i+2][j] > answer)
                answer=map[i][j+1]+map[i+1][j+1]+map[i+2][j+1]+map[i+2][j];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+1][j+2] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+1][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i][j+1]+map[i][j+2]+map[i+1][j+2] > answer)
                answer=map[i][j]+map[i][j+1]+map[i][j+2]+map[i+1][j+2];
        }
    }    
    for(int i=0;i<N-2;++i){ // type 4
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+2][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j+1]+map[i][j+2]+map[i+1][j]+map[i+1][j+1] > answer)
                answer=map[i][j+1]+map[i][j+2]+map[i+1][j]+map[i+1][j+1];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i+1][j]+map[i+2][j]+map[i][j+1]+map[i+1][j+1] > answer)
                answer=map[i+1][j]+map[i+2][j]+map[i][j+1]+map[i+1][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+1][j+2] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+1][j+2];
        }
    }    
    for(int i=0;i<N-1;++i){ // type 5
        for(int j=0;j<M-2;++j){
            if(map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2] > answer)
                answer=map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i+1][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1] > answer)
                answer=map[i+1][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1];
        }
    }
    for(int i=0;i<N-1;++i){
        for(int j=0;j<M-2;++j){
            if(map[i+1][j]+map[i+1][j+1]+map[i][j+1]+map[i+1][j+2] > answer)
                answer=map[i+1][j]+map[i+1][j+1]+map[i][j+1]+map[i+1][j+2];
        }
    }
    for(int i=0;i<N-2;++i){
        for(int j=0;j<M-1;++j){
            if(map[i][j]+map[i+1][j]+map[i+2][j]+map[i+1][j+1] > answer)
                answer=map[i][j]+map[i+1][j]+map[i+2][j]+map[i+1][j+1];
        }
    }
    cout << answer << "\n";
    return 0;
}

처음에는 위와 같이 반복문에서 반복횟수를 제한함으로써 범위를 제한했다. 하지만 이러한 방법으로는 실수가 너무 잦았고, 코드가 길어지는 불편함이 있었다.

#include <iostream>
using namespace std;
int a[500][500];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (j+3 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i][j+3];
                if (ans < temp) ans = temp;
            }
            if (i+3 < n) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+3][j];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+2][j];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j-1 >= 0) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j-1];
                if (ans < temp) ans = temp;
            }
            if (i-1 >= 0 && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i-1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+1 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+1][j+1];
                if (ans < temp) ans = temp;
            }
            if (i-1 >= 0 && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i-1][j+1] + a[i-1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j+1 < m) {
                int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+2][j+1];
                if (ans < temp) ans = temp;
            }
            if (i+1 < n && j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+1][j+2];
                if (ans < temp) ans = temp;
            }
            if (i+2 < n && j-1 >= 0) {
                int temp = a[i][j] + a[i+1][j] + a[i+1][j-1] + a[i+2][j-1];
                if (ans < temp) ans = temp;
            }
            if (j+2 < m) {
                int temp = a[i][j] + a[i][j+1] + a[i][j+2];
                if (i-1 >= 0) {
                    int temp2 = temp + a[i-1][j+1];
                    if (ans < temp2) ans = temp2;
                }
                if (i+1 < n) {
                    int temp2 = temp + a[i+1][j+1];
                    if (ans < temp2) ans = temp2;
                }
            }
            if (i+2 < n) {
                int temp = a[i][j] + a[i+1][j] + a[i+2][j];
                if (j+1 < m) {
                    int temp2 = temp + a[i+1][j+1];
                    if (ans < temp2) ans = temp2;
                }
                if (j-1 >= 0) {
                    int temp2 = temp + a[i+1][j-1];
                    if (ans < temp2) ans = temp2;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

이와 같이, 하나의 반복문에서 if문으로 제한을 두는게 조금 더 보기에 편했다.

#include <iostream>
using namespace std;
int a[500][500];
int block[19][3][2] = {	// 19개의 테트로미노를 미리 정의
    {{0,1}, {0,2}, {0,3}},
    {{1,0}, {2,0}, {3,0}},
    {{1,0}, {1,1}, {1,2}},
    {{0,1}, {1,0}, {2,0}},
    {{0,1}, {0,2}, {1,2}},
    {{1,0}, {2,0}, {2,-1}},
    {{0,1}, {0,2}, {-1,2}},
    {{1,0}, {2,0}, {2,1}},
    {{0,1}, {0,2}, {1,0}},
    {{0,1}, {1,1}, {2,1}},
    {{0,1}, {1,0}, {1,1}},
    {{0,1}, {-1,1}, {-1,2}},
    {{1,0}, {1,1}, {2,1}},
    {{0,1}, {1,1}, {1,2}},
    {{1,0}, {1,-1}, {2,-1}},
    {{0,1}, {0,2}, {-1,1}},
    {{0,1}, {0,2}, {1,1}},
    {{1,0}, {2,0}, {1,1}},
    {{1,0}, {2,0}, {1,-1}},
};
int main() {
    int n, m;
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            for (int k=0; k<19; k++) {
                bool ok = true;
                int sum = a[i][j];
                for (int l=0; l<3; l++) {
                    int x = i+block[k][l][0];
                    int y = j+block[k][l][1];
                    if (0 <= x && x < n && 0 <= y && y < m) {
                        sum += a[x][y];
                    } else {
                        ok = false;
                        break;
                    }
                }
                if (ok && ans < sum) {
                    ans = sum;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

이렇게 코드를 간편화할 수도 잇겠지만, 실전에서는 실력에 맞게 직접 맵핑하는 방식을 사용하는 것이 맞는 것 같다. 코드가 직관적일수록 이해도 빠르고 디버깅도 쉽기 때문이다.