문제 요약
테트로미노는 다음과 같이 5 종류가 있습니다.
N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
아이디어
테트로미노를 4*4 크기의 kernel로 정의하고 conv 연산을 구현했다.
kernel의 왼쪽위 자리를 anchor로 삼고 kernel을 한칸씩 움직여가며(stride = 1) conv 연산을 진행했다.
또한 커널의 종류에 있어서 회전과 대칭을 허용하기 때문에
예를 들어 보라색 커널 하나에 대해서 8개의 버전이 나오게 된다.
(한번 회전한 결과물에 한번 반전)
anchor의 움직임
4*4 kernel과 map이 겹치는 영역이 달랑 한칸인 경우들도 포함을 시켜줬다. 아래 사진은 앵커움직임의 끝과 끝들이다.
7개월 전쯤 플었던 비슷한 카카오 문제에서 앵커 움직임 관련해서 우측 하단 가장자리를 빼먹었던 실수를 했던 적이 있다.
그 실수를 보완해서 풀었다.
또 테트로미노의 경우 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며란 조건 때문에 사실 우측 하단 커널 위치 같은 경우는 포함시키지 않는다.
회전과 반전
하나의 회전 버전에 대해 하나의 반전 버전을 만들면 4*2 = 8 해서 8개 버전이 나오게 된다.
커널 사이즈가 16으로 아주 작기 때문에 O(1) 걸리는 연산이라고 판단하고 마음껏 부르트포스 해줬다...
소스코드
에디터에선 괄호 닫기를 사용해서 커널 정의 부분이랑 카피하는 부분 등을 접어놔서 몰랐는데 길다....
| 대칭선을 사용하는 반전 함수 이름을 transpose라 하지 말걸 그랬다.
2차원 행렬에서 transpose라 함은 (대각선)대칭선을 사용하는 거기때문에...
#include<iostream>
#include<string>
#include<memory.h>
#include<algorithm>
#include<math.h>
using namespace std;
//anchor 개념+회전
//삐져나와선 안됨
int tab[500][500];
int n, m;
int ker[5][4][4];
int ker_a[4][4] = { {1,1,1,1},{0,0,0,0},{0,0,0,0},{0,0,0,0} };
int ker_b[4][4] = {
{1,0,0,0},
{1,0,0,0},
{1,1,0,0},
{0,0,0,0},
};
int ker_c[4][4] = {
{1,0,0,0},
{1,1,0,0},
{0,1,0,0},
{0,0,0,0},
};
int ker_d[4][4] = {
{1,1,1,0},
{0,1,0,0},
{0,0,0,0},
{0,0,0,0},
};
int ker_e[4][4] = {
{1,1,0,0},
{1,1,0,0},
{0,0,0,0},
{0,0,0,0},
};
bool inbox(int i, int j) {
return i >= 0 && i < n&& j >= 0 && j < m;
}
int conv(int k, int ki, int kj) {
int sum = 0;
bool able = true;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (ker[k][i][j] == 1) {
if (inbox(ki + i, kj + j)) {
sum += tab[ki + i][kj + j];
}
else{
//cout << "inbox 실패" << ki + i << "," << kj + j << endl;
sum = -1;
able = false;
break;
}
}
}
if (!able) break;
}
//cout << "conv res : " << k << " , " << ki << " , " << kj<<" : " << sum << endl;
return sum;
}
int max_per_kernel(int k) {
int max_sum = 0;
for (int i = -3; i < n; i++) {//앵커 움직임
for (int j = -3; j < m; j++) {
max_sum = max(max_sum, conv(k, i, j));
}
}
return max_sum;
}
void rot(int k) {//커널 종류
int temp[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
temp[j][3 - i] = ker[k][i][j];
}
}
copy(&temp[0][0], &temp[0][0] + 4 * 4, &ker[k][0][0]);
}
void transpose(int k) {//transpose with vertical line
int temp[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
temp[i][3 - j] = ker[k][i][j];
}
}
copy(&temp[0][0], &temp[0][0] + 4 * 4, &ker[k][0][0]);
}
void print_ker(int c) {
//확인
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cout << ker[c][i][j] << " ";
}
cout << endl;
}
cout << "========================\n";
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> tab[i][j];
}
}
{
copy(&ker_a[0][0], &ker_a[0][0] + 4 * 4, &ker[0][0][0]);
copy(&ker_b[0][0], &ker_b[0][0] + 4 * 4, &ker[1][0][0]);
copy(&ker_c[0][0], &ker_c[0][0] + 4 * 4, &ker[2][0][0]);
copy(&ker_d[0][0], &ker_d[0][0] + 4 * 4, &ker[3][0][0]);
copy(&ker_e[0][0], &ker_e[0][0] + 4 * 4, &ker[4][0][0]);
}
int sum_max = 0;
for (int k = 0; k < 5; k++) {
for (int r = 0; r < 4; r++) {//커널의 종류 회전 정함
//cout << "rotation : " << r << endl;
//print_ker(k);
sum_max = max(sum_max,max_per_kernel(k));
transpose(k);
sum_max = max(sum_max, max_per_kernel(k));
transpose(k);//원상복구, 안해주면 틀린다.
rot(k);
}
}
cout << sum_max << endl;
}후기
이런 종류의 문제는 설명을 열심히 읽는 것으로 사실 풀리긴 한다... 화이트 디버깅이 가능하다는 얘기다. 그래서 문제를 꼼꼼히 읽고 한방에 푸는 게 가장 베스트이다.
근데 종종 조건을 빼먹어서 (이번에는 반전도 가능하다는 걸 못봤었다..) 전체 테케에서 틀리는 경우가 있다. 한번 빼먹은 조건은 다시 읽어도 안 읽힌다.... 그래서 테케를 갖고 점검을 하면서 빼먹은 조건을 찾아내는 과정이 필요하다고 느꼈다.
이런 경우 디버깅을 위한 테케를 어떻게 만들어야하는지 고민이 된다. 이 문제는 커널이 5*4*2로 너무 많은데.. 그리고 앵커의 위치가 가장자리인 경우 역시 왼쪽 오른쪽 위 아래 4가지를 점검해야할 것 같다.
이런 경우 다들 어떻게 테케를 만들어 블랙 디버깅을 하는지 궁금하다..
