알고리즘 문제 올려 봅니다 - 답변 부탁드립니다.

각 게시판의 주제에서 벗어나는 게시물을 삭제 전에 임시로 보관하는 곳입니다. 읽기 전용이나, 자신의 글을 삭제, 수정하는 것은 가능합니다.
Post Reply
비회원

알고리즘 문제 올려 봅니다 - 답변 부탁드립니다.

Post by 비회원 »

딱히 GPG만큼 엄청 잘하시는
프로그래머 분들이 계시는
한국 커뮤니티를 찾을 수 없어 이렇게 알고리즘 문제가 도저히 안풀려 올려봅니다.


////////////////////////////////////////////////////////////////////////////////////////////////////


123

456

789

x0x


위는 일반적인 전화번호 판의 배열의 모습이다.



이상적인 전화번호는


123-4567

456-2780

897-0564 와 같이


중복된 숫자가 안에 있지 않고 (123-4567 은 어느 수 하나 중북되지 않았다, 126-4567이러면 6이 중복된 것이다.)



전체 숫자가 서로 붙어있는 전화번호를 이상적인 전화번호라고 한다.



만일 123-7890 이렇게 되어있다면 이 것은 이상적인 전화번호가 아닌 것이 된다. 왜냐면 번호집합이 서로 떨어져

있기 때문이다.



123-5789는 이상적인 전화번호이다. 왜냐하면 번호들이 서로 이어지기 때문이다.







단 맨 앞에는 0이 올 수 없다. (1~9만 맨 앞에 가능)



이 때 이상적인 전화번호를 모두 구하는 프로그램을 작성하라.









푸시는 분은 좀 짱이 되실듯- 실제 수학적 논리력 사고를 많이 연습하신 용자분 부탁드립니다.



그럼 부탁드립니다!!



감사합니다!!
비회원

아 실례했습니다. 제가 어줍짢게 질문 드린거 같아 일단 사과드립니다.

Post by 비회원 »

일단 몇 시간 고민해 보았던 소스를 올립니다.

123-4567 이 안나와서 그러는데 왜 123-4567이결과 배열에 포함이안되는지 잘 모르겟습니다

주석 달아서 아래에 소스를 붙여 넣습니다 비주얼 스튜디오에서 콘솔로 프로젝트 만들고 붙여넣으시면

딱 결과하면 확인 하실 수 있으실 겁니다- 아무튼 정말 부탁드립니다.

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