백준 14500 G4 테트로미노

문제: 테트로미노

접근: 브루트 포스

테트로미노의 각 정사각형을 픽셀 좌표라고 생각하면 테트로미노 하나를 4개의 pair<int, int> 배열로 표현할 수 있다.

또한, 테트로미노 하나를 시계 방향으로 0, 90, 180, 270도 돌릴 수 있고, 좌 우로 한번 뒤집은 후 0, 90, 180, 270도 돌릴 수 있다. 그러니까, 테트로미노 하나로 총 8개의 모양을 만들어 낼 수 있다.

이 8개의 모양 중 중복되는 것이 분명 있을 것이고, “중복되는 것을 제외하면 어떨까?” 라고 생각해 보았지만, 문제가 너무 복잡해지는 것 같아서 다른 방향으로 접근했다.

그냥 무식하게 풀어도 시간 초과가 나는가 안 나는가에 대해 고민했고, 그 판단을 내린 과정은 다음과 같다:

무식하게 푼다는 것은 중복이 있건 없건 만들어질 수 있는 모든 테트로미노를 대상으로, 각 테트로미노의 4개 좌표 중 하나를 기준으로 삼아, 주어진 점수 보드의 각 칸에 하나씩 다 대입해서 점수를 계산하고 그 최댓값을 갱신하겠다는 것이다.

보드의 크기는 최대 500이고, 한 번 순회에 약 10410^4의 연산이 필요하다.

그리고 보드의 좌표 하나당, 5개의 테트로미노를 대상으로 생성된 각 테트로미노별 8개 모양, 그리고 그 모양별로 4개의 좌표로 점수를 계산해 내야 하므로 보드 한 칸당 총 5 * 8 * 4, 약 10210^2번의 연산이 필요하다.

그, 테트로미노 연산에 중복이 있건 없건 간에 104⋅102=10610^4 \cdot 10^2 = 10^6 밖에 연산이 안 들고 제한시간은 2초이므로 매우 넉넉하다. 중복에 대해 그리 생각할 필요가 없다!

그러니, 무식하게 풀자!

알고리즘

  • 각 테트로미노를 정의할 때, 4개의 두 정수의 쌍으로 정의하되, 기준 정수쌍인 (0,0)(0, 0)을 항상 포함시킨다.
    • 다른 모든 테트로미노의 픽셀 좌표는 (0,0)(0, 0)에 상대적인 좌표로 표현한다.
    • 다시 말해, (0,0)(0, 0)은 테트로미노의 로컬 좌표계 의 기준이다.
  • 5개의 테트로미노를 돌리고 뒤집고 반복해서 테트로미노의 모든 모양을 한 방에 계산하여 배열에 넣어둔다.
    • 이 배열은 중복된 것이 포함되지만 무시하고, 총 갯수가 40개여야 한다.
    • “뒤집고 반복해서” 에 회전 변환 과, 대칭 이동 변환 이 사용된다.
  • 점수판의 각 픽셀에 대해서:
    • 모든 테트로미노에 대해서:
      • 테트로미노의 로컬 좌표를, 점수판의 좌표계로 이동시킨다. (그냥 더하면 된다.)
      • 이동시켰을 때, 점수판의 경계를 넘어서면 반복문의 다음으로 넘어간다.
      • 넘어서지 않으면 점수를 계산하고, 최대값이면 기록한다.

알고리즘 자체는 쉬우나 관리할 정보의 양이 많기 때문에 해당 능력을 테스트하는 문제가 아닌가 싶다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct Tet {
  pair<int, int> poss[4];

  inline static Tet get_global_tet(const Tet& tet, pair<int, int> pivot)  {
    Tet ret{tet};
    for (auto& [x, y]: ret.poss) {
      x += pivot.first;
      y += pivot.second;
    }
    return ret;
  }

  inline static Tet gen_flipped_tets(const Tet& tet) {
    Tet ret{tet};
    for (auto& [x, y]: ret.poss) {
      x = -x;
    }
    return ret;
  }

  inline static vector<Tet> gen_rotated_tets(const Tet& tet) {
    vector<Tet> ret;
    // 0, 90, 180, 270 일 때 값
    static constexpr int cos[] { 1, 0, -1, 0 }; 
    static constexpr int sin[] { 0, 1, 0, -1 };

    for (int i = 0; i < sizeof(cos)/ sizeof(cos[0]); ++i) {
      Tet ctet{tet};

      for (auto& [x, y]: ctet.poss) {
        int n_x = x * cos[i] - y * sin[i];
        int n_y = y * cos[i] + x * sin[i];

        x = n_x;
        y = n_y;
      }

      ret.push_back(ctet);
    }
    return ret;
  }

  inline static vector<Tet> gen_all_transformed_tets(const Tet& tet) {
    vector<Tet> normal_rotated = gen_rotated_tets(tet);
    vector<Tet> flipped_rotated = gen_rotated_tets(gen_flipped_tets(tet));

    normal_rotated.insert(normal_rotated.end(), 
      make_move_iterator(flipped_rotated.begin()),
      make_move_iterator(flipped_rotated.end())
    );
    return normal_rotated;
  }

  inline static bool is_valid_global_tet(int mx, int my, const Tet& g_tet) {
    for (auto& [x, y]: g_tet.poss) {
      if (!(0 <= x && x < mx) || !(0 <= y && y < my)) {
        return false;
      }
    }
    return true;
  }

  inline static int process_score(const vector<vector<int>>& board, const Tet& g_tet) {
    int score{0};

    for (const auto& [x, y]: g_tet.poss) {
      score += board[x][y];
    }

    return score;
  }
};

// 5개 테트로미노의 장의
constexpr Tet T0 {{{ 0,  0}, { 1,  0}, { 2,  0}, { 3,  0}}};
constexpr Tet T1 {{{ 0,  0}, { 1,  0}, { 0,  1}, { 1,  1}}};
constexpr Tet T2 {{{ 0,  0}, { 1,  0}, { 0,  1}, { 0,  2}}};
constexpr Tet T3 {{{ 0,  0}, { 1,  0}, { 1, -1}, { 0,  1}}};
constexpr Tet T4 {{{ 0,  0}, { 1,  0}, { 2,  0}, { 1, -1}}};

// 전체 테트로미노 배열
constexpr Tet TETS[] { T0, T1, T2, T3, T4 };


int main() {
  int N, M; cin >> N >> M; // [4, 500] 한번 순회시 10^4
  // 테트로미노 전체에 대해 매 셀마다 검증해도 10^2 * 10^4 = 10^6 ; 제한시간 OK

  // 점수 입력
  vector<vector<int>> score_map(N, vector<int>(M));
  for (vector<int>& v: score_map) {
    for (int& e: v) {
      cin >> e;
    }
  }

  int max_score{INT_MIN};

  // 모든 테트로미노에 대해 모든 회전 및 대칭 변환을 적용한 결과를 저장
  vector<Tet> all_local_tets;
  for (const Tet& tet: TETS) {
    vector<Tet> c_all = Tet::gen_all_transformed_tets(tet);

    all_local_tets.insert(
      all_local_tets.end(),
      make_move_iterator(c_all.begin()), 
      make_move_iterator(c_all.end())
    );
  }

  // 점수판의 모든 셀에 대해 모든 테트로미노를 넣어보고, 가능한 경우 최대값 찾기
  for (int x = 0; x < score_map.size(); ++x) {
    for (int y = 0; y < score_map[x].size(); ++y) {
      for (const Tet& tet: all_local_tets) {
        Tet g_tet = Tet::get_global_tet(tet, {x, y});

        if (!Tet::is_valid_global_tet(N, M, g_tet)) 
          continue;

        max_score = max(max_score, Tet::process_score(score_map, g_tet));
      }
    }
  }

  // 최대값 출력
  cout << max_score;

  return 0;
}

기타

2차원 좌표의 회전 변환

2차원 공간에서 한 점 (x,y)(x, y)을 원점 (0,0)(0, 0)을 기준으로 반시계 방향으로 θ\theta만큼 회전시키는 공식은 다음과 같다.

x′=xcos⁡θ−ysin⁡θx^\prime = x\cos{\theta}-y\sin{\theta} y′=xsin⁡θ+ycos⁡θy^\prime = x\sin{\theta}+y\cos{\theta}

이를 행렬 형태로 표현하면 아래와 같다.

(x′ y′)=(cos⁡θ−sin⁡θ sin⁡θcos⁡θ)(x y)\begin{pmatrix} x^\prime \\\ y^\prime \end{pmatrix} = \begin{pmatrix} \cos\theta & -\sin\theta \\\ \sin\theta & \cos\theta \end{pmatrix} \begin{pmatrix} x \\\ y \end{pmatrix}

다시한 번 주의할 점은 이게 원점을 기준으로 하는 회전 변환이라는 것이다. 이 문제에서도 그러므로 모든 테트로미노가 로컬 좌표계에서 원점에 붙어 있도록 의도하였다.

범위 기반 for 문은 C 스타일 배열도 순회가 가능하다

T[] 형식으로 선언된 배열에만 해당된다. T*로 Decay 되어버린 배열로는 순회가 안 된다. (이는 배열 형식 자체가 크기에 대한 정보를 가지고 있기 때문)

int[] arr{0, 1, 2};
int* aptr = new int[3];

for (int& e: arr) { /* works */ }
for (int& e: aptr) { /* not works */ }

벡터 합치기

대중적으로 두 가지 방식이 있다. (둘다 캐퍼시티를 초과하면 재할당이 일어나므로 주의한다. 결과 벡터의 길이를 대충 알고있다면, 미리 예약해 두는 것도 좋다.)

첫 번째는:

std::vector<T> dst, src;

dst.insert(
  dst.end(),
  std::make_move_iterator(src.begin()),
  std::make_move_iterator(std.end())
);

반복자 어답터인 std::make_move_iterator를 이용하면 src의 요소에 복사를 발생시키지 않고, 마치 각 요소에 대해 std::move(*it)가 적용된 것처럼 작동한다.

두 번째는:

std::vector<T> dst, src;

std::move(
  src.begin(), 
  src.end(),
  std::back_inserter(dst)
)

둘 다 src를 이동시키기 때문에 연산이 끝난 후 src에 대한 접근을 조심해야 한다. 이동 후에 src.clear()를 써서 가독성을 높여 실수를 방지할 수도 있다. 1

Footnotes

  1. src.clear() 호출 없어도 src 내용을 전부 이동시켰으면 src는 빈 상태가 된다. ↩

← 글 목록