More actions
ZeroPage 03
Profile
컴퓨터 공학과 03학번 손동일입니다 ZP ghost member.. 현재 휴학중입니다.. 자주 이용 할테니.. 페이지 사용할 수 있게 해주세요~^^
폰번호 011-763-5032 엠에센 ajagaja82 at hotmail dot com
목표
언어마스터되기
계획
언어공부하기
진행중
TOEIC , C++, 잠자기.. EMBEDED ( 하나도 모르겠다.. )
Coding....
데블스 캠프를 통해 배운것
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;
}