해밀턴회로

Hamilton Circuit

해밀턴 회로는 모든 정점을 방문하여 처음 출발점으로 돌아 오는 회로이다. 해밀턴 회로를 사용하려면 일단 그래프를 배열로 표현해야 한다. 만일 다음과 같은 그래프가 있다고 하자

<!--[if !vml]--><!--[endif]-->

그래프는 2차원 배열로 나타내게 된다. 간선이 연결된 곳은 1, 그렇지 않은 곳은 0으로 저장한다. 위의 그래프를 배열로 표현하면 다음과 같다.

	1	2	3	4
1	0	1	1	0
2	1	0	1	1
3	1	1	0	1
4	0	1	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);
}