테트로미노(Gold 5)
문제
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
접근법
이번 문제는 테트로미노로 만들 수 있는 모든 모양으로 모든 위치에서 탐색을 수행하여 풀 수 있는 Brute Force 문제입니다. 완전 탐색을 하기 위한 테트로미노 모양을 만들어 내는 방법이 조금 까다로운 구현 문제입니다. 우선 테트로미노 블록은 회전과 대칭을 통해서 만들 수 있는 모양이 총 19가지입니다. 전체 위치는 500 * 500 이기 때문에 각 위치별 19번씩 탐색을 진행하더라도 충분히 시간 내에 탐색을 마칠 수 있습니다.
전체 구현
- 테트로미노 블럭 19개 3차원 배열에 정의합니다.
- 전체 데이터 배열은 좌우상하 0을 가진 여백을 2칸 만들어서 배열 범위를 초과하지 않도록 합니다.
#include <stdio.h>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
int blocks[19][4][2]{
{{0,-1}, {0,0}, {0,1}, {0,2}}, // ㅡ
{{-1,0}, {0,0}, {1,0}, {2,0}},
{{0,0}, {0,1}, {1,0}, {1,1}}, // ㅁ
{{0,0}, {0,1}, {1,1}, {2,1}}, // ㄴ
{{0,0}, {1,0}, {1,-1}, {1,-2}},
{{0,0}, {0,-1}, {-1,-1}, {-2,-1}},
{{0,0}, {-1,0}, {-1,1}, {-1,2}},
{{0,0}, {0,-1}, {1,-1}, {2,-1}},
{{0,0}, {-1,0}, {-1,-1}, {-1,-2}},
{{0,0}, {0,1}, {-1,1}, {-2,1}},
{{0,0}, {1,0}, {1,1}, {1,2}},
{{0,0}, {1,0}, {1,1}, {2,1}}, // z
{{0,0}, {0,1}, {-1,1}, {-1,2}},
{{0,0}, {-1,0}, {-1,1}, {-2,1}},
{{0,0}, {0,1}, {1,1}, {1,2}},
{{0,0}, {1,0}, {1,-1}, {2,0}}, // ㅗ
{{0,0}, {-1,0}, {0,1}, {0,-1}}, // ㅓ
{{0,0}, {1,0}, {1,1}, {2,0}}, // ㅜ
{{0,0}, {1,0}, {0,-1}, {0,1}} // ㅏ
};
int main() {
int N, M; // (4 ≤ N, M ≤ 500)
scanf("%d %d ", &N, &M);
vector<vector<int>> map(N + 4);
for (int i = 0; i < N + 4; ++i)
{
map[i].resize(M + 4, 0);
}
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
scanf("%d ", &map[i + 2][j + 2]);
}
}
int answer{};
for(int i = 2; i < N + 2; ++i)
for(int j = 2; j < M + 2; ++j)
for (int k = 0; k < 19; ++k)
{
int sum{};
for (int n = 0; n < 4; ++n)
{
int row = i + blocks[k][n][1];
int col = j + blocks[k][n][0];
sum += map[row][col];
}
answer = max(answer, sum);
}
printf("%d", answer);
return 0;
}기타
블록들의 배열을 만들때 오류가 발생하면 찾기 어렵습니다. 만약 배열의 값이 잘못 되었는지 의심된다면 아래의 테스트 케이스를 활용하여 디버깅 할 수 있습니다. 아래의 값들을 실행해서 답이 4가 나오는지 확인하면 됩니다.
4 4
1 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0
4 4
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
4 4
1 1 1 0
0 0 1 0
0 0 0 0
0 0 0 0
4 4
1 1 0 0
1 0 0 0
1 0 0 0
0 0 0 0
4 4
1 0 0 0
1 1 1 0
0 0 0 0
0 0 0 0
4 4
0 1 0 0
0 1 0 0
1 1 0 0
0 0 0 0
4 4
1 1 1 0
1 0 0 0
0 0 0 0
0 0 0 0
4 4
1 0 0 0
1 0 0 0
1 1 0 0
0 0 0 0
4 4
0 0 1 0
1 1 1 0
0 0 0 0
0 0 0 0
4 4
1 1 0 0
1 0 0 0
1 0 0 0
0 0 0 0
4 4
1 1 0 0
1 1 0 0
0 0 0 0
0 0 0 0
4 4
1 0 0 0
1 1 0 0
0 1 0 0
0 0 0 0
4 4
0 1 0 0
1 1 0 0
1 0 0 0
0 0 0 0
4 4
1 1 0 0
0 1 1 0
0 0 0 0
0 0 0 0
4 4
0 1 1 0
1 1 0 0
0 0 0 0
0 0 0 0
4 4
0 1 0 0
1 1 1 0
0 0 0 0
0 0 0 0
4 4
1 0 0 0
1 1 0 0
1 0 0 0
0 0 0 0
4 4
0 1 0 0
1 1 0 0
0 1 0 0
0 0 0 0
4 4
1 1 1 0
0 1 0 0
0 0 0 0
0 0 0 0
