/* UVA302 존의 드라이빙
존은 친구들을 만나러 드라이빙을 계획중이다.
친구들은 마을에 있는 도로마다 한명씩 산다.
존은 드라이빙을 마친후 집으로 가장 최단 시간안에 돌아와야 한다.
가장 최단시간에 드라이빙을 마치려면 각각의 도로를 한번씩만 거쳐서 집으로 돌아와야한다.
마을에는 1<=n<1995 범위의 정수이름을 가지는 도로가 존재하며 각각의 도로의 이름은 겹치지 않는다.
도로는 딱 2개의 교차점과만 양끝으로 연결되어 있으며 교차점은 1<=m<44의 정수이름을 가진다.
만약 최적의 드라이브 코스가 여러개면 가장 번호가 낮은 도로를 출력한다.
존은 첫번째 도로에서 더 작은 숫자의 교차점에 산다.
이때 존의 드라이빙을 계획해보자.
Input
x y z// x: 도로 z의 한쪽 끝에 연결된 교차점의 이름, y: 도로 z의 반대쪽에 연결된 교차점
.
.
.
0 0//테스트 데이터의 끝.
또 다른 테스트 데이터 입력 가능
0 0
0 0//빈테스트 데이터로 입력 데이터의 끝
Output
1 2 4 5 3//방문하는 도로를 순서대로 출력. 테스트 데이터 1 결과
Round trip does not exist//테스트 데이터 2 결과. 적합한 코스 없음.
<알고리즘 요약>
교차점을 정점으로 도로를 간선으로 하는 오일러 회로를 그리디 알고리즘을 통해 구한다.
Greedy Euler Path 에서 했던것처럼 일단 어떤 경로로든 더이상 진행할 수 없는 끝점에 도달하고도 간선이 남아 있다면
중간에 지나지 않은 회로들이 존재하는 것이므로(남은 간선들이 모두 정점에 짝수개씩 연결되어 있으므로)
중간에 또다른 회로가 존재하는 정점으로 돌아가서 회로를 검색하고 그 회로를 경로에 중간에 추가해준다.
그러고도 남은 간선이 존재한다면 회로가 존재했던 정점을 다시 검색하고 계속 이전 정점으로 검색하면서
또다른 회로가 존재하면 또 추가해주고 검색하고를 반복하여 모든 간선을 소비할 때 까지 반복한다.
그러나 Greedy Euler Path 에서는 스텍 2개를 이용하여 스텍 사이에 회로를 추가하는 방법을 사용하였는데
연속된 데이터의 중간을 추가하고 삭제하기 편한 연결 리스트 구조를 사용해볼 것이다.
그리고 문제에서 모든 도로에 이름이 있고 도로 이름으로 경로를 구별해야 하므로
간선을 구조체로 만들고 연결 리스트구조로 간선 구조체들을 연결해야 한다.
사전식으로 가장 빠른 경로를 출력하려면 출발점부터 시작하여 각각의 교차로에서
검색이 완료되지 않은 도로중 가장 번호가 낮은 도로로 검색해 나가야 된다.
다음과 같은 형식으로 교차로별 검색 순서를 설정한다.
교차로/ 도로
1 / 3->4->5-> -1
2 / 1->2->5->6 -> -1
3 / 3->6->-1
효울성을 위해 이러한 데이터를 따로 2차원 배열에 저장하지 않고 도로 구조체 배열에 같이 저장한다.
각각의 도로가 연결된 두개의 정점에서 도로를 검색할때
이 도로 다음으로 검색 우선순위가 있는 도로를 저장한다.
따라서 현재 정점에서 해당 도로가 사용되는 순간
구조체에 저장된 다음 검색순위 데이터를 이용하여
다음으로 검색해야할 도로를 갱신한다.
도로 구조체{
x 정점, y 정점 , 번호 z
x 정점에 이 도로 다음의 검색 우선순위를 가진 도로 nextx;
y 정점에 이 도로 다음의 검색 우선순위를 가진 도로 nexty;
다음 도로;
이전도로;
}
input data를 다음과 같은 방식으로 받는다.
|순환문 시작
|[1]x, y ,z를 입력받는다.
|[2]road[x][y][z]에 입력 해준다.
*/
#include <iostream>
#include <algorithm>
#include <windows.h>
#ifdef _MSC_VER
#define min_MIN
#endif
using namespace std;
struct street{
int x,y,z; //연결된 정점정보, 간선정보
int nextx,nexty;//이 도로 다음으로 검색 우선순위를 가진 도로
//각각의 정점에서 이 도로를 방문했을때 갱신해준다 다음 도로
int prev, next;// 이전에 방문한 도로와 다음에 방문할 도로
};
street s[1996];//도로 구조체;
int juncs[45];//각각의 교차점에서 가장 우선적으로 방문해야하는 도로;
int z_cmp(const street a, const street b);
int path(int junc, int &start_street,int &end_street);
int main()
{
int count, junc, start_street, street, i, s1, e1, s2;
bool fail, rep;
while(1){
fail = false;
//도로 배열의 0번 부터 테스트 데이터의 끝이 선언될때 까지 채워나간다.
count = 0;
while(1){
cin>>s[count].x>>s[count].y;
if(s[count].x==0&&s[count].y==0)break;
cin>>s[count++].z;
}
if(count==0)break;//빈테스트 데이터를 입력받으면 입력데이터를 더이상 받지 않는다.
//존은 첫번째로 입력되는 도로의 2개의 교차점중 더 낮은 숫자의 교차점에서 산다.
junc = min(s[0].x,s[0].y);
//같은 길이의 간선일때 더 작은 숫자의 간선을 먼저 출력해야 하므로
//간선번호에 의해 구조체 간선들을 정렬.
sort(s,s+count,z_cmp);
fill(juncs,juncs+45,-1);//교차점 정보 초기화.
//각각의 도로 구조체를 설정.
//각각의 정점에 대해 연결 우선순위 도로를 설정한다. 더이상 없을땐 -1이다.
for(i=count-1;i>=0;i--){
s[i].nextx=juncs[s[i].x];
juncs[s[i].x]=i;
s[i].nexty = juncs[s[i].y];
juncs[s[i].y]=i;
s[i].prev = -1;
s[i].next = -1;
}
//출발점에서 오일러 경로를 방문하여 돌아오는 점이 출발점인지 검사.//
//greedy Euler Path algorithm 이다.
//조건문을 통과해도 오일러 회로가 존재한다고 보장할 수 없다.
//지나지 않은 경로에 간선이 홀수개인 정점이 존재 가능하기 때문이다
if(path(junc,start_street,e1)==junc){
s[start_street].prev=e1;
s[e1].next=start_street;
//연결리스트로 순환하는 회로를 만들어 준다.
//시작 도로을 검사하는 교차로 다음에 연결된 도로에 저장
//따라서 끝점부터 검사를 시작할 수 있다.
street = start_street;
//회로가 두개이상 존재하는 경우 체크
//도착 정점에서 한칸씩 뒤로 돌아가면서 무시된 회로를 검사한다.
do{
//다시 시작점으로 돌아오는 회로가 있는지 검사.
if(path(junc,s1,e1)==junc){//s1은 출발간선, e1 은 도착간선
rep = false;//반복 여부(모든 경로상의 정점에 대한 검사를 못마침 여부)
//현재교차점에서 남은 간선이 있는 경우
//츨발하긴 한 경우
//사실 이 조건문 안에서는(s1=-1<->e1=-1)
if(s1!=-1&&e1!=-1){
//또다른 내부회로를 연결
s2 = s[street].prev;
//또다른 내부회로의 시작 지점 연결
s[s1].prev = s2;
s[s2].next = s1;
//또다른 내부회로의 끝부분 연결
s[street].prev = e1;
s[e1].next = street;
//다시 현재교차점에서 반복
rep = true;
}
//현재 교차점에서 남은 도로가 없는 경우
//출발간선이 없어서 출발 못한 경우
else {
//이전간선으로 이동
street = s[street].prev;
//이전 정점으로 이동해서 경로를 다시 탐색
junc = (s[street].x!=junc)?s[street].x: s[street].y;
//처음으로 돌아오지 않은 경우 반복
//출발정점은 도중에 여러번 중복되어 사용되기 때문에 지표로 사용할 수 없다.
//출발점과 끝점이 같기 떄문에 출발점마저 검사 해줄필요가 없다.
if(street !=start_street)rep= true;
}
}
//중간에 끓기거나 멈춘경우
//도착점이 아닌 점에서 간선이 홀수게인 정점에 도달하게 된것이다.
else{
cout<<"Round trip does not exist."<<endl<<endl;
fail = true;
}
}while(rep && !fail);
//시작 도로까지 거꾸로 해서 탐색이 완료될때 까지 반복
if(!fail){//오일러 회로가 존재할 경우
//시작도로의 번호부터 차례로 출력
cout<<s[start_street].z;
for(i=s[start_street].next;i!=start_street;i=s[i].next){
cout<<" "<<s[i].z;
}
cout<<endl<<endl;
}
}
//출발한 교차점으로 돌아오는 회로가 없는 경우
// 간선이 홀수인 점이 존재하여 그점에서 검색이 멈추었다.
else cout<<"Round trip does not exist"<<endl<<endl;
}
system("PAUSE");
return 0;
}
int z_cmp(const street a, const street b){
return (a.z<b.z);
}
int path(int junc, int &start_street,int &end_street){
int street,i;//방금 지나온 간선, 현재 정점이 진행해야할 간선
street = -1;
//순차적으로 번호를 따라 이동한다.
while(1){
//현재정점에 연결된 다음 간선의 정보를 얻어온다.
i = juncs[junc];
//정점에 연결된 모든 간선이 방문 완료인 경우
if( i == -1){
//처음 부터 진행할 간선이 없다.
if(street == -1) start_street = -1;
//이경우 시작간선이 존재하지 않으며
//마지막 간선 또한 존재하지 않는다.
//또한 회로를 완주하지 않았지만 시작 정점이 반환된다.
//더이상 방문할 간선이 없는 경우 가장
//이전도로가 마지막 간선이 된다.
end_street = street;
return junc;
}
//방문하지 않은 도로인 경우
if(s[i].next == -1){
//간선을 한번도 방문하지 않은 경우
if(street == -1){
//그 이전 간선이 없으므로 -2로 셋팅
s[i].prev = -2;
//첫번째 도로로 셋팅
start_street = i;
}else{
//현재 간선을 i의 이전 간선으로 저장
s[i].prev = street;
//i를 현재 간선의 다음 간선으로 저장
s[street].next = i;
}
//i번 간선의 다음 간선은 아직 정해지지 않았으므로
//-2로 간선이 이미 방문되었음을 나타냄과 동시에 -2로 끝을 나타냄.
s[i].next = -2;
//리스트 구조에서 현재정점에서 다음에 진행해야할 도로를 저장.
juncs[junc] = (s[i].x == junc)?s[i].nextx:s[i].nexty;
//현재 정점에서 i번째 간선을 통해 진행할 정점을 저장
junc = (s[i].x==junc)?s[i].y:s[i].x;
street = i;//i번재 간선을 방금 지났으므로
}
//이미 방문한 도로라면
else{
//다음 우선순위 도로를 현재 가려던 도로의 데이터를 이용해 구한다
juncs[junc] = (s[i].x==junc)?s[i].nextx:s[i].nexty;
}
}
}
실행결과
1 2 1
2 3 2
3 1 6
2 3 3
1 2 5
3 1 4
0 0
1 2 3 5 4 6
1 2 1
2 3 2
2 3 3
1 4 4
0 0
Round trip does not exist
존은 친구들을 만나러 드라이빙을 계획중이다.
친구들은 마을에 있는 도로마다 한명씩 산다.
존은 드라이빙을 마친후 집으로 가장 최단 시간안에 돌아와야 한다.
가장 최단시간에 드라이빙을 마치려면 각각의 도로를 한번씩만 거쳐서 집으로 돌아와야한다.
마을에는 1<=n<1995 범위의 정수이름을 가지는 도로가 존재하며 각각의 도로의 이름은 겹치지 않는다.
도로는 딱 2개의 교차점과만 양끝으로 연결되어 있으며 교차점은 1<=m<44의 정수이름을 가진다.
만약 최적의 드라이브 코스가 여러개면 가장 번호가 낮은 도로를 출력한다.
존은 첫번째 도로에서 더 작은 숫자의 교차점에 산다.
이때 존의 드라이빙을 계획해보자.
Input
x y z// x: 도로 z의 한쪽 끝에 연결된 교차점의 이름, y: 도로 z의 반대쪽에 연결된 교차점
.
.
.
0 0//테스트 데이터의 끝.
또 다른 테스트 데이터 입력 가능
0 0
0 0//빈테스트 데이터로 입력 데이터의 끝
Output
1 2 4 5 3//방문하는 도로를 순서대로 출력. 테스트 데이터 1 결과
Round trip does not exist//테스트 데이터 2 결과. 적합한 코스 없음.
<알고리즘 요약>
교차점을 정점으로 도로를 간선으로 하는 오일러 회로를 그리디 알고리즘을 통해 구한다.
Greedy Euler Path 에서 했던것처럼 일단 어떤 경로로든 더이상 진행할 수 없는 끝점에 도달하고도 간선이 남아 있다면
중간에 지나지 않은 회로들이 존재하는 것이므로(남은 간선들이 모두 정점에 짝수개씩 연결되어 있으므로)
중간에 또다른 회로가 존재하는 정점으로 돌아가서 회로를 검색하고 그 회로를 경로에 중간에 추가해준다.
그러고도 남은 간선이 존재한다면 회로가 존재했던 정점을 다시 검색하고 계속 이전 정점으로 검색하면서
또다른 회로가 존재하면 또 추가해주고 검색하고를 반복하여 모든 간선을 소비할 때 까지 반복한다.
그러나 Greedy Euler Path 에서는 스텍 2개를 이용하여 스텍 사이에 회로를 추가하는 방법을 사용하였는데
연속된 데이터의 중간을 추가하고 삭제하기 편한 연결 리스트 구조를 사용해볼 것이다.
그리고 문제에서 모든 도로에 이름이 있고 도로 이름으로 경로를 구별해야 하므로
간선을 구조체로 만들고 연결 리스트구조로 간선 구조체들을 연결해야 한다.
사전식으로 가장 빠른 경로를 출력하려면 출발점부터 시작하여 각각의 교차로에서
검색이 완료되지 않은 도로중 가장 번호가 낮은 도로로 검색해 나가야 된다.
다음과 같은 형식으로 교차로별 검색 순서를 설정한다.
교차로/ 도로
1 / 3->4->5-> -1
2 / 1->2->5->6 -> -1
3 / 3->6->-1
효울성을 위해 이러한 데이터를 따로 2차원 배열에 저장하지 않고 도로 구조체 배열에 같이 저장한다. 각각의 도로가 연결된 두개의 정점에서 도로를 검색할때
이 도로 다음으로 검색 우선순위가 있는 도로를 저장한다.
따라서 현재 정점에서 해당 도로가 사용되는 순간
구조체에 저장된 다음 검색순위 데이터를 이용하여
다음으로 검색해야할 도로를 갱신한다.
도로 구조체{
x 정점, y 정점 , 번호 z
x 정점에 이 도로 다음의 검색 우선순위를 가진 도로 nextx;
y 정점에 이 도로 다음의 검색 우선순위를 가진 도로 nexty;
다음 도로;
이전도로;
}
input data를 다음과 같은 방식으로 받는다.
|순환문 시작
|[1]x, y ,z를 입력받는다.
|[2]road[x][y][z]에 입력 해준다.
*/
#include <iostream>
#include <algorithm>
#include <windows.h>
#ifdef _MSC_VER
#define min_MIN
#endif
using namespace std;
struct street{
int x,y,z; //연결된 정점정보, 간선정보
int nextx,nexty;//이 도로 다음으로 검색 우선순위를 가진 도로
//각각의 정점에서 이 도로를 방문했을때 갱신해준다 다음 도로
int prev, next;// 이전에 방문한 도로와 다음에 방문할 도로
};
street s[1996];//도로 구조체;
int juncs[45];//각각의 교차점에서 가장 우선적으로 방문해야하는 도로;
int z_cmp(const street a, const street b);
int path(int junc, int &start_street,int &end_street);
int main()
{
int count, junc, start_street, street, i, s1, e1, s2;
bool fail, rep;
while(1){
fail = false;
//도로 배열의 0번 부터 테스트 데이터의 끝이 선언될때 까지 채워나간다.
count = 0;
while(1){
cin>>s[count].x>>s[count].y;
if(s[count].x==0&&s[count].y==0)break;
cin>>s[count++].z;
}
if(count==0)break;//빈테스트 데이터를 입력받으면 입력데이터를 더이상 받지 않는다.
//존은 첫번째로 입력되는 도로의 2개의 교차점중 더 낮은 숫자의 교차점에서 산다.
junc = min(s[0].x,s[0].y);
//같은 길이의 간선일때 더 작은 숫자의 간선을 먼저 출력해야 하므로
//간선번호에 의해 구조체 간선들을 정렬.
sort(s,s+count,z_cmp);
fill(juncs,juncs+45,-1);//교차점 정보 초기화.
//각각의 도로 구조체를 설정.
//각각의 정점에 대해 연결 우선순위 도로를 설정한다. 더이상 없을땐 -1이다.
for(i=count-1;i>=0;i--){
s[i].nextx=juncs[s[i].x];
juncs[s[i].x]=i;
s[i].nexty = juncs[s[i].y];
juncs[s[i].y]=i;
s[i].prev = -1;
s[i].next = -1;
}
//출발점에서 오일러 경로를 방문하여 돌아오는 점이 출발점인지 검사.//
//greedy Euler Path algorithm 이다.
//조건문을 통과해도 오일러 회로가 존재한다고 보장할 수 없다.
//지나지 않은 경로에 간선이 홀수개인 정점이 존재 가능하기 때문이다
if(path(junc,start_street,e1)==junc){
s[start_street].prev=e1;
s[e1].next=start_street;
//연결리스트로 순환하는 회로를 만들어 준다.
//시작 도로을 검사하는 교차로 다음에 연결된 도로에 저장
//따라서 끝점부터 검사를 시작할 수 있다.
street = start_street;
//회로가 두개이상 존재하는 경우 체크
//도착 정점에서 한칸씩 뒤로 돌아가면서 무시된 회로를 검사한다.
do{
//다시 시작점으로 돌아오는 회로가 있는지 검사.
if(path(junc,s1,e1)==junc){//s1은 출발간선, e1 은 도착간선
rep = false;//반복 여부(모든 경로상의 정점에 대한 검사를 못마침 여부)
//현재교차점에서 남은 간선이 있는 경우
//츨발하긴 한 경우
//사실 이 조건문 안에서는(s1=-1<->e1=-1)
if(s1!=-1&&e1!=-1){
//또다른 내부회로를 연결
s2 = s[street].prev;
//또다른 내부회로의 시작 지점 연결
s[s1].prev = s2;
s[s2].next = s1;
//또다른 내부회로의 끝부분 연결
s[street].prev = e1;
s[e1].next = street;
//다시 현재교차점에서 반복
rep = true;
}
//현재 교차점에서 남은 도로가 없는 경우
//출발간선이 없어서 출발 못한 경우
else {
//이전간선으로 이동
street = s[street].prev;
//이전 정점으로 이동해서 경로를 다시 탐색
junc = (s[street].x!=junc)?s[street].x: s[street].y;
//처음으로 돌아오지 않은 경우 반복
//출발정점은 도중에 여러번 중복되어 사용되기 때문에 지표로 사용할 수 없다.
//출발점과 끝점이 같기 떄문에 출발점마저 검사 해줄필요가 없다.
if(street !=start_street)rep= true;
}
}
//중간에 끓기거나 멈춘경우
//도착점이 아닌 점에서 간선이 홀수게인 정점에 도달하게 된것이다.
else{
cout<<"Round trip does not exist."<<endl<<endl;
fail = true;
}
}while(rep && !fail);
//시작 도로까지 거꾸로 해서 탐색이 완료될때 까지 반복
if(!fail){//오일러 회로가 존재할 경우
//시작도로의 번호부터 차례로 출력
cout<<s[start_street].z;
for(i=s[start_street].next;i!=start_street;i=s[i].next){
cout<<" "<<s[i].z;
}
cout<<endl<<endl;
}
}
//출발한 교차점으로 돌아오는 회로가 없는 경우
// 간선이 홀수인 점이 존재하여 그점에서 검색이 멈추었다.
else cout<<"Round trip does not exist"<<endl<<endl;
}
system("PAUSE");
return 0;
}
int z_cmp(const street a, const street b){
return (a.z<b.z);
}
int path(int junc, int &start_street,int &end_street){
int street,i;//방금 지나온 간선, 현재 정점이 진행해야할 간선
street = -1;
//순차적으로 번호를 따라 이동한다.
while(1){
//현재정점에 연결된 다음 간선의 정보를 얻어온다.
i = juncs[junc];
//정점에 연결된 모든 간선이 방문 완료인 경우
if( i == -1){
//처음 부터 진행할 간선이 없다.
if(street == -1) start_street = -1;
//이경우 시작간선이 존재하지 않으며
//마지막 간선 또한 존재하지 않는다.
//또한 회로를 완주하지 않았지만 시작 정점이 반환된다.
//더이상 방문할 간선이 없는 경우 가장
//이전도로가 마지막 간선이 된다.
end_street = street;
return junc;
}
//방문하지 않은 도로인 경우
if(s[i].next == -1){
//간선을 한번도 방문하지 않은 경우
if(street == -1){
//그 이전 간선이 없으므로 -2로 셋팅
s[i].prev = -2;
//첫번째 도로로 셋팅
start_street = i;
}else{
//현재 간선을 i의 이전 간선으로 저장
s[i].prev = street;
//i를 현재 간선의 다음 간선으로 저장
s[street].next = i;
}
//i번 간선의 다음 간선은 아직 정해지지 않았으므로
//-2로 간선이 이미 방문되었음을 나타냄과 동시에 -2로 끝을 나타냄.
s[i].next = -2;
//리스트 구조에서 현재정점에서 다음에 진행해야할 도로를 저장.
juncs[junc] = (s[i].x == junc)?s[i].nextx:s[i].nexty;
//현재 정점에서 i번째 간선을 통해 진행할 정점을 저장
junc = (s[i].x==junc)?s[i].y:s[i].x;
street = i;//i번재 간선을 방금 지났으므로
}
//이미 방문한 도로라면
else{
//다음 우선순위 도로를 현재 가려던 도로의 데이터를 이용해 구한다
juncs[junc] = (s[i].x==junc)?s[i].nextx:s[i].nexty;
}
}
}
실행결과
1 2 1
2 3 2
3 1 6
2 3 3
1 2 5
3 1 4
0 0
1 2 3 5 4 6
1 2 1
2 3 2
2 3 3
1 4 4
0 0
Round trip does not exist
댓글
댓글 쓰기