전개도
아래에 주어진 전개도의 점선 부분을 접어서 주사위 모양의 정육면체를 만들 수 있는지를 생각해 보자.
전개도의 각 면은 1에서 6까지 서로 다른 정수로 표시되어 있다.
전개도 (1)은 정육면체로 접을 수 있지만, 전개도 (2)는 정육면체로 접을 수 없다.
입력으로 주어진 전개도를 정육면체로 접을 수 있는지를 알아보는 프로그램을 작성하시오.
입력형식
입력은 여섯 줄로 되어 있으며 각 줄에는 0 에서 6 까지의 정수들이 여섯 개 있고,
숫자 사이에는 빈칸이 하나씩 있다.
1 에서 6 까지의 숫자는 전개도의 면을 나타내고, 0 은 전개도의 바깥 부분을 나타낸다.
출력형식
입력된 전개도를 정육면체로 접을 수 있으면 정육면체에서 1 번으로 표시된 면의 맞은 편 면의 번호를 출력하고
정육면체로 접을 수 없으면 0 을 출력한다.
입력 예 |
출력 예 |
| 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 |
3 |
| 0 0 0 0 0 0 0 5 0 4 0 0 0 1 2 3 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
0 |
소스코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define Swap(a, b) {t = a; a = b; b = t;}
int a[6][6], b[7], c[7], d[7], t;
int match(int x1, int y1, int x2, int y2 ) {
int i;
if (x1 > x2)
Swap(x1, x2);
if (y1 > y2)
Swap(y1, y2);
if (x2 == x1 + 2)
{
for (i = y1; i <= y2; i++)
{
if (a[x1 + 1][i] == 0)
break;
}
if (i > y2)
return 1;
}
if (y2 == y1 + 2)
{
for (i = x1; i <= x2; i++)
{
if (a[i][y1 + 1] == 0)
break;
}
if (i > x2)
return 1;
}
return 0;
}
int main()
{
int i, j, k;
for (i = 0; i < 6; i++)
{
for (j = 0; j < 6; j++)
{
scanf("%d", &a[i][j]);
b[a[i][j]] = i;
c[a[i][j]] = j;
}
}
for (i = 1; i <= 6; i++)
{
if (d[i] == 0)
{
for (j = i + 1; j <= 6; j++)
{
if (d[j] == 0)
{
if (match(b[i], c[i], b[j], c[j]))
{
d[i] = j;
d[j] = i;
break;
}
}
}
}
}
for (i = 1; i <= 6; i++)
if (d[i] == 0)
break;
if (i > 6)
printf("%d\n", d[1]);
else
printf("0\n");
return 0;
}
