3DMP
2012. 12. 23. 16:19
경로는 그냥 연결된 구조이고
회로란 처음 시작점에서 출발하여 다시 시작점으로 오는구조이다
아래 포스팅한것의 결과를 보면 1에서 출발했다가 다시 1로 왔음을 알 수 있다
퍼오긴했는데 그래프는 안나온다(아래 블로그로 가도 마찬가지)
http://junghong456.tistory.com/11
Hamilton Circuit
해밀턴 회로는 모든 정점을 방문하여 처음 출발점으로 돌아 오는 회로이다. 해밀턴 회로를 사용하려면 일단 그래프를 배열로 표현해야 한다. 만일 다음과 같은 그래프가 있다고 하자
<!--[if !vml]-->
<!--[endif]-->
그래프는 2차원 배열로 나타내게 된다. 간선이 연결된 곳은 1, 그렇지 않은 곳은 0으로 저장한다. 위의 그래프를 배열로 표현하면 다음과 같다.
해밀턴은 정점을 두 번이상 방문하지 않아야 하므로 처음 false 로 해두었다가 한번 방문하면 true로 바꾸어 정점을 체크하는 것만 오일러 코드에 추가하면 해밀턴 코드가 된다. 해밀턴 회로에 대한 입력 예제가 다음과 같다.
입력
4 5
1 2
1 3
2 3
2 4
3 4
출력
1->2->4->3->1
입력의 첫 번째 줄은 정점의 개수와 간선의 개수를 나타낸다. 다음에 간선의 개수 만큼 한 줄씩 간선으로 연결되는 두 정점의 번호가 입력된다.
===========================================================================================================================
문제 자체는 상당히 쉬운 문제이다.
다른 모든 정점을 탐색하기 전에는 시작점으로 가지 않고
탐색했던 정점을 다시 가지 않도록만 해주면 된다.
문제 푸는 방식은 당연히 재귀호출이 편하다.
#include<stdio.h>
#include<stdlib.h>
int p[10][10],n;
int check[10][10];
int g[10];
void input()
{
FILE *fp=fopen("input.txt","r");
int a,x,y,i;
fscanf(fp,"%d %d", &n, &a);
for(i=1;i<=a;i++)
{
fscanf(fp,"%d %d", &x, &y);
p[x][y]=1;
p[y][x]=1;
}
fclose(fp);
}
void process(int k, int cnt)
{ //세팅해주어야 할 것들:
//1. 다른 정점을 모두 탐색하기 전까진 시작점으로 오지 않도록 한다.
//2. 갔던 곳은 가지 않도록 한다.
int i;
if(k==1) //k가 1일때 다음 else if()문을 가지 않게 하는 기능도 한다.
{
if(cnt>n) // 다른 정점을 모두 탐색했을 경우 출력
{
printf("%d ", k);
for(i=1;i<=n;i++)
printf("%d ", g[i]);
printf("\n");
}
}
// 다른 정점을 모두 탐색하지 않았는데 k가 1이라면 return
else if(cnt <= n && k == 1)
return;
for(i=1;i<=n;i++)
{
//갈 수 있는 정점이고 탐색하지 않았던 곳이라면 탐색
if(p[k][i]==1 && check[k][i] == 0)
{
check[k][i]=1;
check[i][k]=1;
g[cnt]=i; // 경로 입력
process(i,cnt+1);
check[k][i]=0;
check[i][k]=0;
}
}
}
void main()
{
int i;
input();
process(1,1);
}
