Even Idiots Can Make Game

백준 14500 G4 테트로미노

Date/Lastmod
Section
PS
Title
백준 14500 G4 테트로미노
Ps-Tags
Solved
03-14/25

#1 접근: 브루트 포스

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

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

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

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

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

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

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

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

그러니, 무식하게 풀자!

#1 알고리즘

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

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

#1 코드

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

#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;
}

#1 기타

#2 2차원 좌표의 회전 변환

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

$$ x^\prime = x\cos{\theta}-y\sin{\theta}
$$ $$ y^\prime = x\sin{\theta}+y\cos{\theta} $$

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

$$ \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} $$

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

#2 범위 기반 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 */ }

#2 벡터 합치기

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

첫 번째는:

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

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

comments powered by Disqus