[BOJ/Platinum 5] 백준 2642 전개도(C++)

문제 링크

https://www.acmicpc.net/problem/2642

2642번: 전개도

문제

아래에 주어진 전개도의 점선 부분을 접어서 주사위 모양의 정육면체를 만들 수 있는지를 생각해 보자. 전개도의 각 면은 1에서 6까지 서로 다른 정수로 표시되어 있다.

전개도 (1)은 정육면체로 접을 수 있지만, 전개도 (2)는 정육면체로 접을 수 없다. 입력으로 주어진 전개도를 정육면체로 접을 수 있는지를 알아보는 프로그램을 작성하시오.

입력

입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나타낸다.

출력

입력된 전개도를 정육면체로 접을 수 있으면, 정육면체에서 1번으로 표시된 면의 맞은 편 면의 번호를 출력하고, 정육면체로 접을 수 없으면 0을 출력한다.

예제 입력 1

0 0 0 0 0 0
0 0 0 0 0 0
0 0 5 0 0 0
0 1 2 3 4 0
0 0 6 0 0 0
0 0 0 0 0 0

예제 출력 1

3

알고리즘 분류

• 구현
• 그래프 탐색

풀이

면 하나가 다른 면과 마주보고, 이것이 세 쌍이 존재한다면 전개도를 정육면체로 만들 수 있다.

면 하나가 다른 면과 마주보려면, 동일한 방향으로 두 칸 이동한 칸이 1~6 사이의 숫자라면 마주보는 데 성공한 것이다.

입력받았을 때 1~6이 모두 존재해야 하며, 그렇지 않은 경우에는 전개도가 될 수 없으므로 0을 출력한다.

1~6이 모두 존재한다면, 각 면마다 마주보는 면을 찾고, 모든 면이 마주보는 면이 있다면 전개도가 될 수 있고, 1번 면과 마주보는 면을 출력한다.

1~6 중 마주보는 면이 존재하지 않는다면 전개도로 정육면체를 만들 수 없으므로 0을 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 7
#define LL long long
#define INF 1e9

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 };

// Depth : Dir방향으로 이동한 횟수, Dir : First에서 이동한 방향, (Y, X) : 현재 칸, First : 처음 DFS를 시작했을 때 숫자(1~6 중 하나)
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])) {
			/*
				현재 칸에서 k방향에 있는 칸이 6X6의 격자를 벗어나지 않고,
				0이 아니며(1~6), 숫자 First에서 출발했을 때 지나친 숫자가 아닌 경우
			*/
			Path[First][Next] = true; // First에서 현재 칸까지 왔음을 경로로써 표시한다.
			if (Dir == -1) { // 현재 k방향이 최초로 설정한 방향인 경우
				DFS(1, k, nextY, nextX, First);
			}
			else if ((Dir == k) && (Depth == 1) && ((Face[First] == 0) || (Face[First] == Next)) && ((Face[Next] == 0) || (Face[Next] == First))) {
				/*
					k방향으로 이동 중인데 현재 이동할 방향 역시 k방향이고, 이미 k방향으로 이동하면서 1~6까지의 숫자 중 하나를 만나고 왔으며
					First와 현재 칸(Next) 서로 마주보는 면을 아직 만나지 않았을 때
				*/
				Face[First] = Next;
				Face[Next] = First;
				DFS(Depth + 1, Dir, nextY, nextX, First);
			}
			else {
				/*
					k방향으로 이동 중인데 현재 이동할 방향이 k방향도 아니라면
				*/
				DFS(Depth, Dir, nextY, nextX, First);
			}
		}
	}
}

int main() {
	FIRST
	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);
			}
		}
	}
	// 1부터 6까지의 면을 탐색
	for (int i = 1; i <= 6; i++) {
		int Y = Pos[i].first;
		int X = Pos[i].second;
		if ((Y == 0) && (X == 0)) { // 1~6을 입력받지 않은 경우
			continue;
		}
		Path[i][i] = true;
		DFS(0, -1, Y, X, i); // 방향 미정
	}
	for (int i = 1; i <= 6; i++) { // 1~6 중에 마주보는 면이 없는 경우에는 정육면체로 접을 수 없다.
		if (Face[i] == 0) {
			answer = false;
			break;
		}
	}
	if (answer) {
		cout << Face[1] << "\n";
	}
	else {
		cout << 0 << "\n";
	}

	return 0;
}