BOJ 1917

27 Feb 2020 • ProblemSolving

정육면체 전개도

문제출처

문제 해석

  • 주어지는 6x6배열에 있는 전개도가 정육면체 전개도인지 맞추는 문제입니다.

설계(10)

  • 정육면체의 전개도의 모양의 종류는 총 11가지로, 검색을 통해 해당 모양을 알 수 있었습니다.
  • 11가지의 전개도에 대해 rotation과 flip을 조합하여 모두 탐색하면 정육면체 전개도인지 맞출 수 있습니다.O(11x4x2)
  • 6x6 배열에 대해 모두 탐색을 하므로 시간안에 해결이 가능합니다.
  • 정해진 전개도의 종류를 벡터로 미리 저장해놓은 후, rotate함수와 flip함수를 구현하여 모든 종류의 전개도를 검사하도록 하였습니다.

구현(60)

코드
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 6
vector<vector<vector<int> > > v = { { {0,0,0,1},{1,1,1,1},{0,0,1,0} },
{ {0,0,0,1},{1,1,1,1},{0,1,0,0} },
{ {0,0,0,1},{1,1,1,1},{1,0,0,0} },
{ {0,0,1,0},{1,1,1,1},{0,0,1,0} },
{ {0,0,1,0},{1,1,1,1},{0,1,0,0} },
{ {0,0,1,1},{1,1,1,0},{0,1,0,0} },
{ {0,0,1,1,1},{1,1,1,0,0} },
{ {0,0,1,1},{1,1,1,0},{0,0,1,0} },
{ {0,0,1,1},{1,1,1,0},{1,0,0,0} },
{ {0,0,1,1},{0,1,1,0},{1,1,0,0} },
{ {0,0,0,1},{1,1,1,1},{0,0,0,1} } };

int map[MAXN][MAXN];
bool flag;
void rotate(vector<vector<int> >& vt){
    int N = vt.size();
    int M = vt[0].size();
    vector<vector<int> > tmp(M,vector<int>(N));
    for (int i = 0; i < N; i++){
        for (int j = 0;j <M; j++){
            tmp[j][N-i-1] = vt[i][j];
        }
    }
    vt = tmp;
}
void flip(vector<vector<int> >& vt){
    int N = vt.size();
    int M = vt[0].size();
    vector<vector<int> > tmp(N,vector<int>(M));
    for (int i = 0 ;i  < N; i++){
        for (int j = 0 ;j<M;j++){
            tmp[i][M-j-1] = vt[i][j];
        }
    }
    vt = tmp;
}
bool is_match(int x, int y, vector<vector<int> > vt){
    int N = vt.size();
    int M = vt[0].size();
    for (int i = 0; i <N; i++){
        for (int j=0;j<M;j++){
            if (map[i+x][j+y] != vt[i][j]) return false;
        }
    }
    return true;
}
void simulate(vector<vector<int> >  vt){

    for (int i = 0 ; i< 4; i++){
        for (int j = 0 ;j < 2; j++){
            if (i && !j) rotate(vt);
            if (j) flip(vt);
            int N = vt.size();
            int M = vt[0].size();
            for (int x = 0 ; x <= MAXN-N; x++){
                for (int y = 0 ; y <= MAXN-M; y++){
                    if (is_match(x,y,vt)) {
                        flag = true;
                        return;
                    }
                }
            }
            if (j) flip(vt);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int time = 3;
    while (time--){
        flag = false;
        for (int i = 0 ;i < MAXN; i++){
            for (int j = 0;j<MAXN; j++){
                cin >> map[i][j];
            }
        }
        for (int i = 0 ;i < v.size(); i++){
            simulate(v[i]);
            if (flag) {
                break;
            }
        }
        if (flag) cout <<"yes\n";
        else cout <<"no\n";
    }
    return 0;
}
디버깅
  • 디버깅에 시간이 굉장히 오래걸렸습니다.
  • 제가 실수한 부분은 두가지입니다.
  • 첫번째로, 6x6배열을 탐색할 때의 범위를 잘못설정하였습니다. 이로인해 마지막열은 검사가 되지 않았습니다.
  • 두번째로, (i&&!j)인경우 rotate를 하고, j>0 인경우 flip을 하도록 하였는데 이럴 경우 모든 경우의 모양을 탐색할 수 없는 경우가 생기는 것을 디버깅을 통해 알게 되었습니다.
  • 이를 방지하고자 flip을 한 경우에, 탐색을 마친 후 다시 flip을 하여 원래 모양으로 되돌려놓는 추가 구현을 하였습니다.
제출결과
  • 0ms

마무리

  • 단순 시뮬레이션 문제였습니다. 그러나, 크리티컬한 실수로인해 풀이하는데 시간이 오래걸렸습니다.
  • 앞으로 범위체크, 논리적인 설계를 철저히 할 필요가 있을 것 같습니다.
 BOJ

Related Posts