[BOJ] 백준 2642 전개도 (KOI 1999 초등부)

문제 링크

www.acmicpc.net/problem/2642

2642번: 전개도

 

풀이

실제로 정육면체를 굴려주는 구현을 하면 됩니다. 

전개도를 탐색하며 처음 만나는 면을 밑면으로 잡고, dfs로 탐색하며 큐브를 굴려줍시다.

 

정육면체를 만들 수 없는 경우는 다음과 같습니다.

1) 입력받은 전개도에서 0이 아닌 수가 6개가 아님

2) dfs가 끝난 후 큐브의 6개 면이 다 채워지지 않음

 

정답 코드

#include <bits/stdc++.h>

#define ft first
#define sd second

using namespace std;
using pii = pair<int, int>;

int p[10][10];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

struct Cube {
    int l, r, f, b, u, d;
    int cnt;

    Cube() {
        l = r = f = b = u = d = cnt = 0;
    }

    void rotate(int &x, int &y, int &z, int &w) {
        int tmp = x;
        x = y, y = z, z = w, w = tmp;
    }

    void rotate(int k) {
        if (k == 0) rotate(d, r, u, l);
        else if (k == 1) rotate(d, f, u, b);
        else if (k == 2) rotate(d, l, u, r);
        else rotate(d, b, u, f);
    }

    int getDown() {
        return d;
    }

    void setDown(int x) {
        d = x;
        cnt++;
    }

    int getAns() {
        if (l == 1) return r;
        if (r == 1) return l;
        if (u == 1) return d;
        if (d == 1) return u;
        if (b == 1) return f;
        if (f == 1) return b;
    }
};

bool chk[10][10];

bool isValid(int x, int y) {
    return 0 < x && x < 7 && 0 < y && y < 7;
}

bool dfs(Cube &cube, int now, int x, int y) {
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (isValid(nx, ny) && p[nx][ny] && !chk[nx][ny]) {
            chk[nx][ny] = true;
            int next = p[nx][ny];
            cube.rotate(k);
            if (cube.getDown() != 0) {
                return false;
            } else {
                cube.setDown(next);
            }
            dfs(cube, next, nx, ny);
            cube.rotate((k + 2) % 4);
        }
    }
    return true;
}

int main() {
    int cnt = 0;
    int sx, sy;
    for (int i = 1; i < 7; i++) {
        for (int j = 1; j < 7; j++) {
            cin >> p[i][j];
            if (p[i][j] > 0 && ++cnt == 1) {
                sx = i;
                sy = j;
            }
        }
    }
    Cube cube;
    if (cnt != 6 || !dfs(cube, p[sx][sy], sx, sy) || cube.cnt != 6) {
        cout << 0;
        return 0;
    }
    cout << cube.getAns();
}