BOJ

BOJ::2598 기둥만들기

BOJ Gold Platinum 5

BOJ::2598 기둥만들기

시사점

키

이해(6)

설계, 손 코딩(54)

시간 복잡도

공간 복잡도

손 코딩 후 문제 리뷰(2)

구현(28)

함수 List

// 각 옆 면에 {R,B,G,Y}가 포함되어있는지, mp에 이미 중복된 상태는 없는지 체크합니다.
bool check(char brr[R][C]);

// 가->바->다->마 방향으로 shift합니다.
void shiftUp(char* arr);

// 가->나->다->라 방향으로 shift합니다.
void shiftRight(char* arr);

// mp에 현재 상태 * 4 를 모두 push합니다.
void push(char brr[R][C]);

// 정육면체의 가능한 모든 경우의 수를 생성합니다.
void permute(int cur, char(&now)[R][C]);

업데이트 되는 변수

map<string,int> mp; // 길이 17인 string 상태를 담습니다.

실제 구현

#include<bits/stdc++.h>
const int R = 4, C = 6, CUBES = 4, MAXSHUFFLE = 4;
const int fr = 0, ri = 1, bk = 2, le = 3, up = 4, dn = 5;
using namespace std;

int ans = 0;
char input[R][C];
map<string,int> mp; // 길이 17인 string 상태를 담습니다.

// 각 옆 면에 {R,B,G,Y}가 포함되어있는지, mp에 이미 중복된 상태는 없는지 체크합니다.
bool check(char brr[R][C]){
    char arr[R][C];
    memcpy(arr, brr, sizeof(arr));
    string str = "";
    // 각 옆 면마다 {R, B, G, Y}가 포함되어 있는지 체크합니다.
    for(int j = 0; j < C-2; j++){     // 실수 : 6열 다 체크함.. 4열까지만 체크하면 되는데..
        map<char,int> tmp;            // 실수 : i, j 바꿔서 씀
        for(int i = 0; i < R; i++){
            if(tmp.count(arr[i][j]) > 0) return false;
            tmp[arr[i][j]] = 1;
            if(j < 4)
                str += arr[i][j];
        }
    }

    str += arr[R-1][C-2];
    // 중복된 상태가 mp에 들어있는지 체크합니다.
    if(mp.count(str) > 0)
        return false;

    return true;
}

// 가->바->다->마 방향으로 shift합니다.
void shiftUp(char* arr){
    char tmp = arr[up];
    arr[up] = arr[bk];
    arr[bk] = arr[dn];
    arr[dn] = arr[fr];
    arr[fr] = tmp;
}

// 가->나->다->라 방향으로 shift합니다.
void shiftRight(char* arr){
    char tmp = arr[le];
    arr[le] = arr[bk];
    arr[bk] = arr[ri];
    arr[ri] = arr[fr];
    arr[fr] = tmp;
}

// mp에 현재 상태 * 4 를 모두 push합니다.
void push(char brr[R][C]){
    char arr[R][C]={0};
    memcpy(arr, brr, sizeof(arr));
    for(int i = 0; i < MAXSHUFFLE; i++){
        string str = "";
        for(int j = 0; j < R; j++){
            shiftRight(arr[j]);
        }
        for(int k = 0; k < C-2; k++){ // 실수 : C-2까지만 해야하는데, 전체를 넣음
            for(int l = 0; l < R; l++){
                str += arr[l][k];
            }
        }
        str += arr[3][4]; // 실수 : 마지막 뚜껑 부분 안 더함
        mp[str] = 1;
    }
}

// 정육면체의 가능한 모든 경우의 수를 생성합니다.
void permute(int cur, char(&now)[R][C]){
    if(cur == CUBES){
        if(check(now)){
            push(now);
            ans ++;
        }
        return;
    }
    char origin[R][C];
    memcpy(origin, now, sizeof(origin));
    // 총 24가지의 경우의 수 : 바닥면 1개 고정 후, 우 방향으로 미는 경우의 수 : 6 * 4
    // 앞 위 뒤 아래 :: 16가지
    for(int i = 0; i < 4; i++){
        shiftUp(now[cur]);
        for(int j = 0; j < 4; j++){
            shiftRight(now[cur]);
            permute(cur+1, now);
        }
    }
    // 8가지, 좌 우 면이 바닥면인 경우
    // shiftR 1번하고
    shiftRight(origin[cur]);

    // shiftU 1번 한거랑, 3번한거
    shiftUp(origin[cur]);
    for(int i = 0; i < 4; i++){
        shiftRight(origin[cur]);
        permute(cur+1, origin);
    }
    shiftUp(origin[cur]);
    shiftUp(origin[cur]);
    for(int i = 0; i < 4; i++){
        shiftRight(origin[cur]);
        permute(cur+1, origin);
    }
}

int main(){
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++)
            cin >> input[i][j];

    char now[R][C]={0};
    memcpy(now, input, sizeof(now));
    permute(0, now);
    cout << ans << endl;
    return 0;
}
2nd try(120m)
  • 저번보다 조금 더 깔끔하게 구현한 것 같습니다.
  • 이해(14), 설계(26), 구현(22), 디버깅(40)
  • fixed_all 이라는 배열을 하나 둡니다.
    • bottom을 고정시킨다고 생각하고 6개만 선언을 해줍니다.
    • 이후 precalc를 돌며, bottom을 고정한 회전된 것들을 모두 채워줍니다.
    • 이후, 24개의 모든 모양을 모두 갖추게 됩니다.
// memory violation : 20m
// 24개인데 6 *4 씩 돌림 ( 이미 6개 들어있는데도
// 30m : 조건 빼먹고 구현함.. 한 열에 RGBY가 다 있어야 하지만, 체크안함
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int n = 4, m = 6, MAXPOS = 24;
enum{fr = 0, ri = 1, ba = 2, le = 3, to = 4, bo = 5};
using namespace std;

map<char, int> chk;
map<string, int> mp;
vector<int> asd;
char oa[n][m];
int fixed_all[MAXPOS][6] = { {0,1,2,3,4,5}, {0,3,2,1,5,4}, {4,1,5,3,2,0}, {1,4,3,5,0,2}, {4,0,5,2,1,3}, {0,4,2,5,3,1} };

template <typename tp>
void fixed_rotate(tp *x){
    tp tmp = x[ri];
    x[ri] = x[fr];
    x[fr] = x[le];
    x[le] = x[ba];
    x[ba] = tmp;
}
void precalc(){
    int cnt = 6;
    rep(i, 0, 6){
        int tmp[6];
        memcpy(tmp, fixed_all[i], sizeof(tmp));
        rep(j, 0, 3){
            fixed_rotate(tmp);
            memcpy(fixed_all[cnt], tmp, sizeof(tmp));
            cnt++;
        }
    }
}
void apply(char* x, int idx, int num){
    char tmp[6]; memcpy(tmp, oa[idx], sizeof(tmp));
    rep(i, 0, 6){
        x[i] = tmp[fixed_all[num][i]];
    }
}
void count(char (&a)[n][m]){
    bool f = true;
    string s = "";
    rep(cnt, 0, 4){
        rep(idx, 0, 4){
            fixed_rotate(a[idx]);
        }
        s = "";
        rep(j, 0, n) rep(i, 0, 4) s += a[i][j];
        s += a[n-1][to];
        if(mp.find(s) != mp.end()){
            f = false;
            break;
        }
    }
    if(f) mp[s]++;
}
bool possible(char (&a)[n][m]){
    rep(j, 0, n){
        chk.clear();
        rep(i, 0, 4){
            if(chk.find(a[i][j])!= chk.end()) return false;
            chk[a[i][j]]++;
        }
    }
    return true;
}
void process(){
    precalc();
    rep(i, 0, n) rep(j, 0, m) cin >> oa[i][j];

    char a[n][m];
    memcpy(a, oa, sizeof(a));
    rep(i, 0, MAXPOS){
        apply(a[0], 0, i);
        rep(j, 0, MAXPOS){
            apply(a[1], 1, j);
            rep(k, 0, MAXPOS){
                apply(a[2], 2, k);
                rep(l, 0, MAXPOS){
                    apply(a[3], 3, l);
                    if(possible(a))
                        count(a);
                }
            }
        }
    }

    cout << mp.size() << endl;
}
int main(){
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}

구현 후 코드리뷰 + 예제 돌려보기(x)

디버깅(90)

        for(int k = 0; k < C-2; k++){ // 실수 : C-2까지만 해야하는데, 전체를 넣음
            for(int l = 0; l < R; l++){
                str += arr[l][k];
            }
        }

2nd try

  • (20m) : memory violation 을 일으켰습니다.
    • 최초 선언한 6개에 대해, 각각을 기준으로 3번씩만 돌리면 되지만 4번씩 돌렸습니다.
    • 해당 violation때문에, 선언해둔 다른 전역변수에 접근만하면 에러가 났습니다.
  • (20m) : 최대한 함수를 재활용하고, 로직을 간단하게 하려고 설계하느라,
    • 정작 문제에서 요구하는 바인, 한 열에 모든 색이 들어가는 조건을 빼먹고 구현했습니다.

좋은 코드

풀이
정육면체들을 주어진 조건을 만족하도록 쌓는 방법의 가짓수를 구하는 문제로, 상태
공간을 탐색하는 문제이다. 문제에서 모든 가능한 경우를 구하라고 되어 있는데, 실제
로 가능한 경우의 수가 얼마 되지 않으므로 하나씩 해 보면서 그 중 조건을 만족하는
경우가 몇 가지인지를 세면된다. 우선 한 개의 정육면체를 쌓는 가짓수는 총 6*4=24가지가 있다. 따라서 이러한 경
우를 모든 정육면체에 대해서 따져주면 되는데, 좀 더 생각해 보면 각 기둥의 옆면에
네 가지 색이 모두 나타나는 경우만 검사하면 충분함을 알 수 있다. 따라서 이러한
조건을 벗어나는 경우를 제외하도록 하면 불필요한 탐색을 줄일 수 있다. 또한 문제에서 회전을 통해서 같은 모양이 되는 것은 제외해야 한다고 하였으므로, 조건에 맞는 정육면체를 쌓은 후에는 이를 비교하는 과정을 수행해야 한다. 즉, 이렇
게 네 개의 정육면체를 모두 쌓은 뒤 만들어진 기둥이 지금까지 만들어진 기둥과 회
전하여 같아지지 않는지 검사해 주면 된다. 만일 같아지는 경우가 없다면 새로 만들
어진 경우를 답에 추가하고, 경우의 수를 하나 증가시킨다

#include <fstream>
using namespace std;
#define INFILE "input.txt"
#define OUTFILE "output.txt"
#define code_length 17
ifstream fin(INFILE);
ofstream fout(OUTFILE);
char cube[4][6], code[18], save[1000][18];
int pattern[6][6] = { {4, 5, 0, 1, 2, 3}, {5, 4, 0, 3, 2, 1}, {0, 2, 1, 4, 3, 5}, {2, 0, 1, 5, 3, 4},{1, 3, 0, 5, 2, 4},
    {3, 1, 0, 4, 2, 5} };
int m;
void swap(char &a, char &b)
{
    char c = a; a = b, b = c;
};
void input()
{
    char s[100];
    for (int i=0;i<4;i++)
    {
        fin.getline(s, 255);
        for (int j=0;j<6;j++)
            cube[i][j] = s[j];
    }
}
void code_shift()
{
    for (int i=0;i<4;i++)
    {
        swap(code[i * 4 + 0], code[i * 4 + 1]);
        swap(code[i * 4 + 1], code[i * 4 + 2]);
        swap(code[i * 4 + 2], code[i * 4 + 3]);
    }
}
void code_check()
{
    int i, sw, same = 0;
    for (i=0;i<4;i++)
    {
        if (same == 0)
            for (int j=0;j<m;j++)
            { sw = 0;
                for (int k=0;k<code_length;k++)
                    if (code[k] != save[j][k]) sw = 1;
                if (sw == 0) same = 1;
            }
        code_shift();
    }
    if (same == 0)
    {
        for (i=0;i<code_length;i++)
            save[m][i] = code[i];
        m++;
    }
}
void process(int p)
{
    int i, j, k;
    for (i=0;i<4;i++)
        for (j=0;j<p-1;j++)
            if (code[(p - 1) * 4 + i] == code[j * 4 + i]) return;
    if (p == 4)
        code_check();
    else
        for (i=0;i<6;i++) // pattern
            for (j=0;j<4;j++)
            {
                for (k=0;k<4;k++)
                    code[p * 4 + k] = cube[p][pattern[i][2 + (j + k) % 4]];
                if (p == 3) code[16] = cube[p][pattern[i][0]];
                process(p + 1);
                if (cube[p][2] == cube[p][3] && cube[p][3] == cube[p][4] &&
                    cube[p][4] == cube[p][5]) break;
                if (cube[p][2] == cube[p][4] && cube[p][3] == cube[p][5] &&
                    cube[p][2] != cube[p][3] && j == 1) break;
            }
}
void output()
{
    fout << m << endl;
    fout.close();
}
void main()
{
    input();
    process(0);
    output();
}

최적화