[C++] 백준 - 14500 : 테트로미노

문제 링크

14500번: 테트로미노

 

풀이 ) 완전 탐색

  우선 각 테트로미노 모양을 모두 배열 형태로 만들어 놓는다.

  이 때 모양이 안겹치고 빠뜨리는 게 없도록 조심해야된다. 필자는 여러 번 실수했다.

  그리고 나서는 가장 첫 번째 행 첫 번째 열부터 시작하여 각 모양으로 확인을 한다. 이때 각 행 열이 판에서 벗어나지 않는지 검사를 하여 벗어나는 경우 다음 반복문으로 넘어간다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int type[19][3][2] = {{{0, 1}, {0, 2}, {0, 3}},
                    {{1, 0}, {2, 0}, {3, 0}},
                    {{0, 1}, {1, 0}, {1, 1}},
                    {{0, 1}, {0, 2}, {1, 2}},
                    {{0, 1}, {0, 2}, {-1, 2}},
                    {{0, 1}, {0, 2}, {1, 0}},
                    {{0, 1}, {0, 2}, {-1, 0}},
                    {{1, 0}, {2, 0}, {2, 1}},
                    {{1, 0}, {2, 0}, {2, -1}},
                    {{1, 0}, {2, 0}, {0, 1}},
                    {{1, 0}, {2, 0}, {0, -1}},
                    {{1, 0}, {1, 1}, {2, 1}},
                    {{1, 0}, {1, -1}, {2, -1}},
                    {{0, 1}, {1, 1}, {1, 2}},
                    {{0, 1}, {-1, 1}, {-1, 2}},
                    {{1, 0}, {1, 1}, {2, 0}},
                    {{1, 0}, {1, -1}, {2, 0}},
                    {{0, 1}, {1, 1}, {0, 2}},
                    {{0, 1}, {-1, 1}, {0, 2}}};

int main(void)
{
    int n, m, ans = 0, cand, flag, xx, yy;
    int arr[501][501] = {0, };

    scanf("%d%d", &n, &m);

    for(int i  = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            scanf("%d", &arr[i][j]);

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            for(int k = 0; k < 19; ++k){
                flag = 0;
                for(int l = 0; l < 3; ++l){
                    xx = j+type[k][l][0];
                    yy = i+type[k][l][1];
                    if(xx >= m || xx < 0 || yy >= n || yy < 0){
                        flag++;
                        break;
                    }
                }
                if(flag)
                    continue;
                else{
                    cand = arr[i][j] + arr[i+type[k][0][1]][j+type[k][0][0]] + arr[i+type[k][1][1]][j+type[k][1][0]] + arr[i+type[k][2][1]][j+type[k][2][0]];
                    ans = max(ans, cand);
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

 

주의점 )

- 모양 중복

- 종류 수(19가지)

- 인덱스 범위