baekjoon 14500:테트로미노

baekjoon 14500 테트로미노

14500번 테트로미노

접근

각 테트로미노마다 회전 모양, 대칭 모양을 다 미리 생각해서 상대 좌표를 미리 저장해놓고 모든 칸에 대해 직접 올려보는 방법. 어느 위치를 기준으로 상대좌표를 생각할 지는 크게 중요한 것 같지 않다. 어짜피 모든 칸이 다 종이에 올라가야하니깐 뭘 기준으로 하든 안되는 경우는 어디서든 걸릴 거고 되는 경우는 기준이 동일 한 경우에 중복 카운팅은 되지 않을 것이다.

코드

#include <iostream>
#include <vector>
using namespace std;
const int coverType[19][4][2] = {
  {{0, 0}, {0, 1}, {0, 2}, {0, 3}},
  {{0, 0}, {1, 0}, {2, 0}, {3, 0}},
  {{0, 0}, {0, 1}, {1, 0}, {1, 1}},
  {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
  {{0, 0}, {1, 0}, {2, 0}, {2, -1}},
  {{0, 0}, {1, 0}, {2, 0}, {0, 1}},
  {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
  {{0, 0}, {1, 0}, {1, 1}, {1, 2}},
  {{0, 0}, {1, 0}, {1, -2}, {1, -1}},
  {{0, 0}, {1, 0}, {0, 1}, {0, 2}},
  {{0, 0}, {0, 1}, {0, 2}, {1, 2}},
  {{0, 0}, {1, 0}, {1, 1}, {2, 1}},
  {{0, 0}, {1, 0}, {1, -1}, {2, -1}},
  {{0, 0}, {0, 1}, {1, 1}, {1, 2}},
  {{0, 0}, {0, 1}, {-1, 1}, {-1, 2}},
  {{0, 0}, {0, 1}, {0, 2}, {1, 1}},
  {{0, 0}, {0, 1}, {0, 2}, {-1, 1}},
  {{0, 0}, {0, 1}, {1, 1}, {-1, 1}},
  {{0, 0}, {1, 0}, {2, 0}, {1, 1}}
};
int tryCover(vector<vector<int>>& board, int type);
int main (){
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, m;
  cin >> n >> m;

  //board 만들기
  vector<vector<int>> board(n);
  for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++){
      int temp;
      cin >> temp;
      board[i].push_back(temp);
    }
  }
  int globalMaxSum = 0;
  for (int i = 0; i < 19; i++){
    int sum = tryCover(board, i);
    if (sum > globalMaxSum) globalMaxSum = sum;
  }
  cout << globalMaxSum;
  

  
  
  return 0;
}
int tryCover(vector<vector<int>>& board, int type){

  int n = board.size();
  int m = board[0].size();
  int maxSum = 0;
  for(int i = 0 ; i < n; i++){
    for(int j = 0; j < m; j++){
      int tempSum = 0;
      for(int k = 0; k < 4; k++){
        int ny = i + coverType[type][k][0];
        int nx = j + coverType[type][k][1];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m) tempSum = INT32_MIN;
        else{
          tempSum += board[ny][nx];
        }
      }
      if (tempSum <= 0) continue;

      if (maxSum < tempSum) maxSum = tempSum;
    }
  }
  return maxSum;
}

다른 접근

다른 답변들을 보니까 dfs로 접근한 경우도 꽤 있었다. ‘ㅗ’ 빼고 나머지는 dfs로 접근할 수 있어보인다.

배운 점

일단 모든 문제를 접근 했을 때 가장 먼저 브루트포스를 생각해봐야한다는 거다. 가장 기본은 브루트포스이다. 생각했을 때 제한시간 안에 못할 것 같을 때 다른 생각을 하기 시작한다.