일단 몇 시간 고민해 보았던 소스를 올립니다.
Code: Select all
//이상적인 전화번호 문제
#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>
//STL쓰는게 편한 거 같다.
//실제 올림피아드 대회에서 STL을 사용하게 해 주는지는 모르겠다.
//STL자체가 기본적 자료구조나 알고리즘을 포함한 거니까 안될지도.. 아니면 문제 푸는데 편하라고 될지도..
using namespace std;
//전화번호판 생김새
//123
//456
//789
//x0x
//전화번호 하나를 저장할 수 있는 구조체
struct sInt7
{
public:
sInt7()
{
for(int i = 0; i < 7; i++)
e[i] = 255;
}
int e[7];
};
queue<sInt7> g_qQueue;
vector<sInt7> g_vRes;
int g_nArray[9 + 1][8];
//배열의 연결된 것을 표시, 원래 255대신 -1로 하다가 뭔가 잘 안되서 하다보니 그냥 다 255로 통일했다
//255는 사실상 NULL과 같다.
void MakeConnectArray()
{
for(int i = 0; i < (9 + 1); i++)
for(int j = 0; j < 8; j++)
g_nArray[i][j] = 255;
//0번은 7, 8, 9와 연결되어 있다
int nArray0[8] = {7, 8, 9, 255, 255, 255, 255, 255};
memcpy(g_nArray[0], nArray0, sizeof(nArray0));
//1번은 2, 4, 5번과 연결되어 있다. 아래는 모두 동일.
int nArray1[8] = {2, 4, 5, 255, 255, 255, 255, 255};
memcpy(g_nArray[1], nArray1, sizeof(nArray1));
int nArray2[8] = {1, 3, 4, 5, 6, 255, 255, 255};
memcpy(g_nArray[2], nArray2, sizeof(nArray2));
int nArray3[8] = {2, 5, 6, 255, 255, 255, 255, 255};
memcpy(g_nArray[3], nArray3, sizeof(nArray3));
int nArray4[8] = {1, 2, 5, 7, 8, 255, 255, 255};
memcpy(g_nArray[4], nArray4, sizeof(nArray4));
int nArray5[8] = {1, 2, 3, 4, 6, 7, 8, 9};
memcpy(g_nArray[5], nArray5, sizeof(nArray5));
int nArray6[8] = {2, 3, 5, 8, 9, 255, 255, 255};
memcpy(g_nArray[6], nArray6, sizeof(nArray6));
int nArray7[8] = {4, 5, 8, 0, 255, 255, 255, 255};
memcpy(g_nArray[7], nArray7, sizeof(nArray7));
int nArray8[8] = {4, 5, 6, 7, 9, 0, 255, 255};
memcpy(g_nArray[8], nArray8, sizeof(nArray8));
int nArray9[8] = {5, 6, 8, 0, 255, 255, 255, 255};
memcpy(g_nArray[9], nArray9, sizeof(nArray9));
}
//배열에서 비어 있는 곳을 찾는다 255는 NULL과 같이 하기로 정했으므로 255가 있으면 그곳이 빈 곳이다.
int SearchEmptyIndex(int o[7])
{
for(int i = 0; i < 7; i++)
if(o[i] == 255)
return i;
return 255;
}
//결과 배열에 이미 저장된 결과인가? 중복 결과를 피하기 위해서 만든 함수.
bool IsAlreayInNumber(sInt7& o)
{
//만일 배열에 한개라도 없다면 일단 무조건 넣는다.
if(0 >= g_vRes.size())
return false;
for(unsigned int i = 0; i < g_vRes.size(); i++)
{
sInt7& temp = g_vRes[i];
for(int j = 0; j < 7; j++)
{
if( temp.e[j] != o.e[j] )
break;
else
{
//중복 발생
if(j == 7)
return true;
}
}
}
//중복이 아니다.
return false;
}
//배열에 num이라는 숫자가 하나라도 있는가?
//전화번호안에 중복 숫자를 피하기 위해 만든 함수
//123-3456 에서 3이 중복된다 이러면 안 된다.
bool IsNumberAlreadyInArray(int arry[7], int num)
{
for(int i = 0; i < 7; i++)
{
if(arry[i] == num)
return true;
}
return false;
}
//하나의 번호를 맨 앞의 숫자로 하는 전화번호의 모든 경우의 수 구하기
void MakeIdenticalNumbers(int o)
{
sInt7 seed;
seed.e[0] = o;
//Queue를 썻다 Queue를 쓰면 BFS식으로 탐색 하는 거라고 배운 기억이 난다.
//Stack이 DFS인 듯, 뭐 어쨋든 모든 경우의 루트를 탐색하면 된다.
g_qQueue.push(seed);
while(g_qQueue.size() > 0)
{
sInt7 temp = g_qQueue.front();
g_qQueue.pop();
int index;
if( 255 == (index = SearchEmptyIndex(temp.e)) )
{
if( false == IsAlreayInNumber(temp) )
g_vRes.push_back(temp);
}
else
{
// for(int j = 0; j <= (index - 1); j++)
// {
// int num = temp.e[j];
// if(num == 255)
// continue;
//모든 경우의 수를 다 계산해 주려면 위의 주석 처리된 for 문을 돌리는 게 맞다고 생각들지만, 이상하게
//어디선가 무한 루프가 도는지 너무 계산할게 많은지.. 결과가 나오질 않고 프로그램만 돈다.
//그래서 일단 아래의 int num = temp.e[index - 1]; 로만 수행
int num = temp.e[index - 1];
for(int i = 0; i < 8; i++)
{
if(g_nArray[num][i] != 255)
{
if(false == IsNumberAlreadyInArray(temp.e, g_nArray[num][i]))
{
temp.e[index] = g_nArray[num][i];
g_qQueue.push(temp);
}
}
}
// }
}
}
}
//1~9번 까지를 맨 처음 번호로 하는 모든 전화번호 구하기
void MakeAllIdenticalNumbers()
{
//맨 앞에 0이 나오는 건 인정하지 않는 것으로 한다.
for(int i = 1; i <= 9; i++)
{
MakeIdenticalNumbers(i);
}
}
//결과 출력
void PrintResult()
{
for(unsigned int i = 0; i < g_vRes.size(); i++)
{
sInt7& temp = g_vRes[i];
for(int j = 0; j < 7; j++)
printf("%d ", temp.e[j]);
printf("\n");
if( (i % 20) == 0 && i > 0
)
system("PAUSE");
}
}
int main(int argc, char *argv[])
{
MakeConnectArray();
MakeAllIdenticalNumbers();
PrintResult();
system("PAUSE");
return EXIT_SUCCESS;
}