[Implementation] 백준 28217, 두 정삼각형

  이 문제를 풀기 위해서는 삼각형 행렬의 120도 회전과 대칭 operation을 구현해야 한다. 대칭 operation의 경우는 단순히 중간점을 기준으로 좌우를 swap해주면 되기 때문에 생각보다 간단하게 구현할 수 있다. 그런데 120도 회전을 구현하는 부분은 고민이 필요해서 생각보다 시간이 많이 걸릴 수 있다. 

 삼각형을 3번 회전 시키면 원래 자리로 돌아오기 때문에 우리가 필요한 구현은 삼각형의 120도 3번 회전 했을 때의 배열과 각각 회전한 상태에서 대칭 시키는 구현을 포함해서 총 6개의 행렬만 있으면 비교가 가능하다. A를 모두 회전 시키면 B는 특별히 회전 시킬 필요가 없다. 이 구현만 한다면 나머지는 두 행렬을 비교하는 부분만 남는다. 

 회전을 구현하는 부분은 다양하게 구현할 수 있는데, 아래 두가지 방법을 비교해 보자. 위의 방법은 2차원 배열의 크기를 초기화 한후 1차원 배열은 초기화 하지 않은 상태에서 push_back을 밀어 넣는 방법이다. 1차원 배열 초기화 하지 않는 점은 좋지만, for문의 인덱스가 좀 복잡해 보인다.  아래 방법은 2차원 크기를 초기화 하고, 다시 1차원 크기도 각각 초기화한 상태에서 index에 맞춰 값을 대입하는 방법이다. i, j 모두 0에서 시작해서 상당히 깔끔한 방법이다. 개인의 기호에 따라 취사 선택하면 되겠다. 

// 반시계 방향 회전, 2개 배열을 받아서 대입 
void rot(vvi &ori, vvi &trans) {
    trans = vvi(n); // 배열 크기 초기화 
    int l = n-1;
    for(int i=l; i>=0; --i) {
        for(int j=i; j<n; ++j) {
            trans[l-i].push_back(ori[j][i]);
        }
    }
}
// 시계 방향 회전 
vector<vector<int> > rotate(const vector<vector<int> > &A) {
    int n = (int)A.size();
    vector<vector<int> > ans = vector<vector<int>  > (n); // 백터 크기 초기화
 
    for(int i = 0; i < n; i++) {
        ans[i] = vector<int> (i+1); // 세부 크기 할당
    }
    for(int i = 0; i < n; i++) { // i와 j를 0부터 시작하는 편이 어쩌면 생각이 덜 복잡해 지는 방법
        for(int j = 0; j <= i; j++) {
            ans[i][j] = A[n-1-j][i-j];
        }
    }
    return ans;
}

 회전하는 부분만 구현하고 위의 6개의 상태만 고려할 수 있다면 논리는 생각보다 간단한 문제다. 전체 코드를 살펴보기 바란다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)

using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vb = vector<bool>;

// Formulating 35, Solving 52, success
// 접근 방법 자체가 나쁘지 않지만 회전하는 부분의 구현에서 시간을 많이 잡아 먹음
const int INF = 1e9;
int n;
vector<vvi> arr(8);

// 반시계 방향 회전, 2개 배열을 받아서 대입 
void rot(vvi &ori, vvi &trans) {
    trans = vvi(n); // 배열 크기 초기화 
    int l = n-1;
    for(int i=l; i>=0; --i) {
        for(int j=i; j<n; ++j) {
            trans[l-i].push_back(ori[j][i]);
        }
    }
}
// 시계 방향 회전 
vector<vector<int> > rotate(const vector<vector<int> > &A) {
    int n = (int)A.size();
    vector<vector<int> > ans = vector<vector<int>  > (n); // 백터 크기 초기화
 
    for(int i = 0; i < n; i++) {
        ans[i] = vector<int> (i+1); // 세부 크기 할당
    }
    for(int i = 0; i < n; i++) { // i와 j를 0부터 시작하는 편이 어쩌면 생각이 덜 복잡해 지는 방법
        for(int j = 0; j <= i; j++) {
            ans[i][j] = A[n-1-j][i-j];
        }
    }
    return ans;
}

void oppo(vvi &ori) {
    for(int i=0; i<n; ++i) {
        int l = 0, r = i;
        while(l<r) {
            swap(ori[i][l], ori[i][r]);
            ++l, --r;
        }
    }
}

int check(vvi &arr1, vvi &arr2) {
    int ans = 0;
    for(int i=0; i<n; ++i) 
        for(int j=0; j<=i; ++j) 
            if(arr1[i][j] != arr2[i][j]) ++ans;
    return ans;
}


void solve() {
    cin >> n;
    int ans = INF;
    for(int i=0; i<2; ++i) {
        arr[i] = vvi(n);
        for(int j=0; j<n; ++j) {
            for (int k=0; k<=j; ++k) {
                int t;
                cin >> t;
                arr[i][j].push_back(t);
            }
        }
    }
    rot(arr[0], arr[2]), rot(arr[0], arr[3]);
    oppo(arr[3]);
    ans = min(ans, check(arr[1], arr[2]));
    ans = min(ans, check(arr[1], arr[3]));
    rot(arr[2], arr[4]), rot(arr[2], arr[5]);
    oppo(arr[5]);
    ans = min(ans, check(arr[1], arr[4]));
    ans = min(ans, check(arr[1], arr[5]));
    rot(arr[4], arr[6]), rot(arr[4], arr[7]);
    oppo(arr[7]);
    ans = min(ans, check(arr[1], arr[6]));
    ans = min(ans, check(arr[1], arr[7]));
    cout << ans << '\n';
}

int main() {
    fastio;
    solve();
    return 0;
}