[백준 14500] 테트로미노

이 문제는 어렵지 않은 하드코딩 문제이지만, 디버깅을 하는 과정에서 항상 놓치고 있던 것을 머릿속에 각인시키고자 글을 쓴다.

 

전략

---

내가 문제에 사용한 전략은 아래와 같다.

1. 모든 원소마다 19개의 테트로미노의 최댓값을 비교한다.

2. 테트로미노의 시작점은 최대한 좌측 상단에 있는 정사각형이다.

3. 시작점으로부터 가장 왼쪽에 있는 정사각형과의 거리에 따라서 type을 정한다.

    ->가장 왼쪽에 있는 사각형의 index가 0보다 작지 않게 하기 위해서

4. 모든 원소에 초깃값으로 매우 큰 음수값을 넣어서 경계를 신경 쓰지 않도록 한다.

 

이러한 전략을 적용한 테트로미노 19개의 모양은 아래와 같다.

위와 같은 전략을 사용하여 코딩을 했을 때, 대부분의 경우는 옳은 답이 나온다.

디버깅

---

하지만, 4번의 전략으로 오른쪽, 아래쪽 경계를 신경쓰지 않았기 때문에
주어진 배열의 크기인 n,m이 최대치인 500일 경우, 경계를 넘는 값을 참조하여 틀린 값들이 나왔다.

예를 들어, 아래와 같은 배열이 주어졌을 때

경곗값을 검사하지 않았기 때문에, 테트로미노가 아래와 같이 위치하는 경우도 생겼다.

이러한 경우들을 방지하기 위해서 처음에 잡아놓는 배열의 크기를 503(최대로 참조할 수 있는 범위) 로 늘렸고,

503의 index까지 초깃값을 -4000으로 세팅해주었다.

코드

---

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

using namespace std;
int a[MAX+2][MAX+2];

int type0(int i, int j){
  // 해당 행/열 반대방향으로 블럭이 없는경우
  int maxCount=0;
  int cnt;
  
  //1
  cnt = a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
  if(maxCount<cnt) maxCount=cnt;

  //2
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i][j+3];
  if(maxCount<cnt) maxCount=cnt;

  //3
  cnt = a[i][j]+a[i+1][j]+a[i+2][j]+a[i+3][j];
  if(maxCount<cnt) maxCount=cnt;

  //4
  cnt = a[i][j]+a[i+1][j]+a[i+2][j]+a[i+2][j+1];
  if(maxCount<cnt) maxCount=cnt;

  //5
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j];
  if(maxCount<cnt) maxCount=cnt;

  //6
  cnt = a[i][j]+a[i][j+1]+a[i+1][j+1]+a[i+2][j+1];
  if(maxCount<cnt) maxCount=cnt;

  //9
  cnt = a[i][j]+a[i+1][j]+a[i+1][j+1]+a[i+1][j+2];
  if(maxCount<cnt) maxCount=cnt;

  //10
  cnt = a[i][j]+a[i][j+1]+a[i+1][j]+a[i+2][j];
  if(maxCount<cnt) maxCount=cnt;

  //11
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+2];
  if(maxCount<cnt) maxCount=cnt;

  //12
  cnt = a[i][j]+a[i+1][j]+a[i+1][j+1]+a[i+2][j+1];
  if(maxCount<cnt) maxCount=cnt;
  
  //15
  cnt = a[i][j]+a[i][j+1]+a[i+1][j+1]+a[i+1][j+2];
  if(maxCount<cnt) maxCount=cnt;

  //16
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+1];
  if(maxCount<cnt) maxCount=cnt;
   
  //19
  cnt = a[i][j]+a[i+1][j]+a[i+1][j+1]+a[i+2][j];
  if(maxCount<cnt) maxCount=cnt;

  return maxCount;
}

int type1(int i, int j){
  int maxCount=0;
  int cnt;
  //8
  cnt = a[i][j]+a[i+1][j]+a[i+2][j]+a[i+2][j-1];
  if(maxCount<cnt) maxCount=cnt;

  //13
  cnt = a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j-1];
  if(maxCount<cnt) maxCount=cnt;

  //14
  cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+2][j-1];
  if(maxCount<cnt) maxCount=cnt;

  //17
  cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+2][j];
  if(maxCount<cnt) maxCount=cnt;

  //18
  cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+1][j+1];
  if(maxCount<cnt) maxCount=cnt;

  return maxCount;
}

int type2(int i, int j){
  int cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+1][j-2];
  return cnt;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  for(int i=0; i<=MAX+2; i++){
    for(int j=0; j<=MAX+2; j++){
      // 최솟값을 미리 넣어놓기
      a[i][j]=-5000;
    }
  }

  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 maxCount=0;
  int cnt;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cnt=type0(i,j);
      if(maxCount<cnt) maxCount=cnt;

      if(j-1>=0){
        cnt=type1(i,j);
        if(maxCount<cnt) maxCount=cnt;
      }

      if(j-2>=0){
        cnt=type2(i,j);
        if(maxCount<cnt) maxCount=cnt;
      }
    }
  }
  cout<<maxCount;
  return 0;
}