백준 2642 / 전개도

문제

풀이

정육면체를 완성할 수 있는 전개도를 만족하는 조건은 다음과 같다.
1. 입력 받았을 때 1~6까지의 수가 모두 존재해야 한다.
2. 면하나가 다른 면과 서로 마주보는 쌍이 3쌍이 되어야 한다.
3. 그 만족하는 쌍을 만들기 위해서 하나의 면이 같은 방향으로 두번 이동하였을 때 값이 1~6까지의 값 중 하나여야 한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 7

using namespace std;
bool answer = true;
int MAP[MAX][MAX];
pair<int, int> Pos[MAX];
int Face[MAX];
bool Path[MAX][MAX];
int moveY[4] = {-1, 0, 1, 0};
int moveX[4] = {0, -1, 0, 1};

void DFS(int Depth, int Dir, int Y, int X, int First) {
    for (int k = 0; k < 4; k++) {
        int nextY = Y + moveY[k];
        int nextX = X + moveX[k];
        int Next = MAP[nextY][nextX];
        if ((nextY >= 1) && (nextY <= 6) && (nextX >= 1) && (nextX <= 6) && (Next > 0) && (!Path[First][Next])) {
            Path[First][Next] = true;
            if (Dir == -1) {
                DFS(1, k, nextY, nextX, First);
            } else if((Dir == k) && (Depth == 1) && ((Face[First] == 0) || (Face[First] == Next)) && ((Face[Next] == 0) || (Face[Next] == First))) {
                Face[First] = Next;
                Face[Next] = First;
                DFS(Depth + 1, Dir, nextY, nextX, First);
            }
            else {
                DFS(Depth, Dir, nextY, nextX, First);
            }
        }

    }
}

int main() {
    for (int i = 1; i <= 6; i++) {
        for (int j = 1; j <= 6; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] > 0) {
                Pos[MAP[i][j]] = make_pair(i, j);
            }
        }
    }

    for (int i = 1; i <= 6; i++) {
        int Y = Pos[i].first;
        int X = Pos[i].second;
        if ((Y == 0) && (X == 0)) {
            continue;
        }
        Path[i][i] = true;
        DFS(0, -1, Y, X, i); // 방향 미정
    }

    for (int i = 1; i <= 6; i++) {
        if (Face[i] == 0) {
            answer = false;
            break;
        }
    }
    if (answer) {
        cout << Face[1] << "\n";
    } else {
        cout << 0 << "\n";
    }
    return 0;
}

새로 알게된 지식

출처