손동일

ZeroPage 03

Profile

컴퓨터 공학과
03학번 손동일입니다
ZP ghost member..
현재 휴학중입니다.. 
자주 이용 할테니..  페이지 사용할 수 있게 해주세요~^^ 

폰번호  011-763-5032
엠에센  ajagaja82 at hotmail dot com

목표

언어마스터되기

계획

언어공부하기

http://gostart.net/

진행중

TOEIC , C++, 잠자기..
EMBEDED ( 하나도 모르겠다.. )

Coding....

손동일/TelephoneBook

데블스 캠프를 통해 배운것

python, scheme, squeet, java, 리눅스, OOP

하고싶은 것

실컷 잠자기, LINUX, VB

좋은 프로그램

구구단/손동일 피보나치/손동일 파스칼삼각형/손동일 숫자야구/손동일 만년달력/손동일,aekae

삽질하기..

8queen/손동일 스택큐/손동일 RandomWalk/손동일 오목/재선,동일

---

홈페이지분류, ZeroWikian DuplicatedPage

#include <iostream>
using namespace std;

const int Max = 11	;

struct vertex{
	int going;  
	int goal; 
	int length; 
};

int Vertex[Max][Max] =	
{
	{0,3,100,100,5,100,100,4,100,100,100},  	
	{3,0,2,100,5,7,100,100,100,100,100},	
	{100,2,0,3,100,2,6,100,100,100,100},	
	{100,100,3,0,100,100,7,100,100,100,2},	
	{5,5,100,100,0,4,100,7,100,100,100},	
	{100,7,2,100,4,0,4,5,4,3,100},			
	{100,100,2,7,100,4,0,100,100,4,6},		
	{4,100,100,100,7,5,100,0,2,100,100},	
	{100,100,100,100,100,4,100,2,0,6,100},	
	{100,100,100,100,100,3,4,100,6,0,5},	
	{100,100,100,2,100,100,6,100,100,5,0}	
};

vertex ver1[11] = {(0,0,0),(0,0,0),(0,0,0),
(0,0,0),(0,0,0),(0,0,0),
(0,0,0),(0,0,0),(0,0,0),
(0,0,0),(0,0,0)};

int temp; 
int temp1[10] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 

int soo = 0;
int soo2 = 1; 

int first = 0; 
int last = 0;

int n = Max; 

int between[Max]; 
int check[Max]; 

void shortpath(int Vertex[Max][Max],int between[Max], int n, int check[Max]);
void using_v(int n);
int choose(int between[Max],int n,int check[Max]);

int main()
{
	cout << "최단 경로를 구해보자~ !!!";
	cout << endl;
	cout << "A=0 , B=1 , C=2 , D=3 , E=4 , F=5"
		<< ", G=6 , H=7 , I=8 , J=9 , Z=10 입니다.. "
		<< endl;
	cout << "숫자로 입력하세요";
	cout << endl;
	cout << "첫값을 입력해 주세요.. : " ;
	cin >> first;
	cout << "도착 할 값을 입력해주세요.. : " ;
	cin >> last;
	cout << endl;
	
	int between[Max];
	shortpath(Vertex,between,n,check);
	
	cout << "최단거리 : " << between[last] << "\n";  
	
	cout << "최단경로 : " ;
	cout.put(first+65);
	cout << " ---> "; 
	
	for(int j = soo ; j >= 0 ; j--) 
	{
		if(ver1[j].length == between[last] && ver1[j].goal == last)
		{
			temp1[0] = ver1[j].going;
			temp = ver1[j].going;
		}
	}
	
	for(int l = soo ; l >= 0 ; l--)
	{
		if(temp == -1) 
			break;
		
		using_v(temp);    
	}
	
	for(int m=9 ; m>=0 ; m--) 
		if(temp1[m] != -1)
		{
			if(temp1[m]==10)
			{
				cout.put(temp1[m]+80);
				cout << " ---> ";
			}
			else
			{
				cout.put(temp1[m]+65);
				cout << " ---> ";
			}
		}
		
		if(last==10)
		{
			cout.put(last+80);
			cout << endl; 
		}
		else 
		{
			cout.put(last+65);
			cout << endl;
		}
		
		return 0;
}


void using_v(int n)
{
	int a = n;
	
	for(int k = soo ; k >= 0 ; k--)
	{	
		if(ver1[k].goal == a)
		{
			temp1[soo2] = ver1[k].going;
			temp = ver1[k].going;
			soo2++;	
		}
		
		if(temp == 1 || temp == 4 || temp == 7 ) 
			temp = -1;
	}
}



void shortpath(int Vertex[Max][Max],int between[Max], int n, int check[Max])
{
	int i,j,k;
	
	for(i=0 ; i<n ; i++)  
	{
		check[i] = false;
		between[i] = Vertex[first][i];
	}
	
	check[first]=true; 
	
	for(i=0 ; i<n-2 ; i++)
	{
		j = choose(between,n,check);
		if(j == last)
			break;
		
		check[j] = true;
		
		for(k=0 ; k<n ; k++)
		{
			if(!check[k])
				if(between[j]+Vertex[j][k] < between[k]) 
				{	
					ver1[soo].going = j; 
					
					ver1[soo].goal = k;
					ver1[soo].length = between[j] + Vertex[j][k];
					soo++;
					
					between[k] = between[j] + Vertex[j][k];
				}
		}		
	}
}


int choose(int between[Max],int n,int check[Max])
{
	int minimum,min_price;
	minimum = Max;
	min_price=-1;
	for(int i=0 ; i<n ; i++)
	{
		if(between[i]< minimum && !check[i]) 
		{
			minimum = between[i];
			min_price = i;
		}
	}
	return min_price; 
}

#include <iostream.h>
#include <climits>

const int MAX = 11;
enum {a='a', b='b', c='c', d='d', e='e', 
		f='f', g='g', h='h', i='i', j='j', z='z'};

struct sVertice
{
	int name;
	int neighbor[MAX][2];
	int len_from_start;
	bool except;
};

void main()
{
	sVertice vertices[MAX] = 
	{
		{a, {{b,3}, {e,5}, {h,4}} },
		{b, {{a,3}, {e,5}, {f,7}, {c,2}} },
		{c, {{b,2}, {f,2}, {g,6}, {d,3}} },
		{d, {{c,3}, {g,7}, {z,2}} },
		{e, {{a,5}, {b,5}, {f,4}, {h,7}} },
		{f, {{b,7}, {e,4}, {h,5}, {i,4}, {j,3}, {g,3}, {c,2}} },
		{g, {{f,4}, {j,4}, {z,6}, {d,7}, {c,6}} },
		{h, {{a,4}, {e,7}, {f,5}, {i,2}} },
		{i, {{h,2}, {j,6}, {f,4}} },
		{j, {{i,6}, {f,3}, {g,4}, {z,5}} },
		{z, {{d,2}, {g,6}, {j,5}} },
	};
	cout << "시작점과 끝점을 입력해주세요(a,b,c,d,e,f,g,h,i,j,z) : " << endl;
	char start, end;
	cin >> start >> end;
	
	sVertice * choice;
	sVertice * goal;
	for (int i = 0 ; i < MAX ; i++)
	{
		if ( vertices[i].name == (int)start )
		{
			choice = &vertices[i];
			vertices[i].len_from_start = 0;
		}
		else 
		{
			if ( vertices[i].name == (int)end )
				goal = &vertices[i];
			vertices[i].len_from_start = INT_MAX;
		}
	}
	
	while ( choice != goal )
	{
		for (i = 0 ; i < MAX ; i++)
		{
			for (int j = 0 ; j < MAX ; j++)
			{
				if (vertices[i].except)
					break;
				else if (&vertices[i] == choice)
					break;
				else if (vertices[i].neighbor[j][0] == choice->name)
				{
					if (vertices[i].len_from_start == INT_MAX)
					{
						vertices[i].len_from_start = 0;
						vertices[i].len_from_start
							+= vertices[i].neighbor[j][1]
								+ choice->len_from_start;
					}
					else if (vertices[i].len_from_start
						 - vertices[i].neighbor[j][1]
						 - choice->len_from_start > 0)
						vertices[i].len_from_start
							= vertices[i].neighbor[j][1]
								+ choice->len_from_start;
					break;
				}
			}
		}

		choice->except = true;

		choice = goal;
		for (i = 0 ; i < MAX ; i++)
			if (vertices[i].len_from_start < INT_MAX
			&& !vertices[i].except
			&& (choice->len_from_start == 0
				|| vertices[i].len_from_start < choice->len_from_start))
				choice = &vertices[i];
	}

	cout << "최단거리는 " << goal->len_from_start << "입니다." <<endl;

	char path[MAX];
	int z = 0;
	while (choice->len_from_start != 0)
	{
		for ( i = 0; i < MAX  ; i++)
		{
			if (vertices[i].except)
			{
				for ( int j = 0 ; j < MAX ; j++)
					if (vertices[i].name == choice->neighbor[j][0]
					&& vertices[i].len_from_start 
						== choice->len_from_start - choice->neighbor[j][1])
					{
						path[z++] = char(choice->name);
						choice = &vertices[i];
						break;
					}
			}
		}
	}
	path[z] = char(choice->name);
	cout << "경로는 ";
	for (i = z ; i >= 0 ; i--)
		cout << path[i] << " ";
	cout << endl;
}