Algorithm :: 해밀턴 순환회로

* 정보 올림피아드 1681번 문제입니다.

 지하철 문제와 비슷하지만 차이점만 생각하면 쉽게 풀 수 있습니다. 연습을 위해 새로 풀었습니다.

1. 모든 도시를 순회하고 마지막에 출발 도시로 돌아온다.
2. 모든 도시가 연결되어 있지 않을 수도 있다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 12

typedef struct _stack
{
	int top;
	int cost;
	int city[MAX_N];
} stack;

int N, min_cost = 0x7FFFFFFF;
int city[MAX_N][MAX_N];
stack current_path, min_path;

void push(stack *path, int data);
int pop(stack *path);
int peek(stack *path);
int sum_cost(stack *path);
int exist(stack *path, int data);
void travel();

int main()
{
	FILE *fin = fopen("input.txt", "r"), *fout = fopen("output.txt", "w");
	int i, j;

	fscanf(fin, "%d", &N);
	for(i = 0 ; i < N ; i++)
	{
		for(j = 0 ; j < N ; j++)
		{
			fscanf(fin, "%d", &city[i][j]);
		}
	}

	push(&current_path, 1);
	for(i = 2 ; i <= N ; i++)
	{
		if(!exist(&current_path, i) && city[peek(&current_path) - 1][i - 1] != 0)
		{
			push(&current_path, i);
			travel();
		}
	}

	fprintf(fout, "%d", min_cost);

	fclose(fin);
	fclose(fout);
	return 0;
}

void push(stack *path, int data)
{
	if(path->top < MAX_N)
	{
		path->city[path->top] = data;
		path->top++;
	}
}

int pop(stack *path)
{
	int ret = 0;
	if(path->top > 0)
	{
		path->top--;
		ret = path->city[path->top];
	}
	return ret;
}

int peek(stack *path)
{
	return path->city[path->top - 1];
}

int sum_cost(stack *path)
{
	int i, sum = 0;

	for(i = 0 ; i < path->top - 1 ; i++)
	{
		sum += city[path->city[i] - 1][path->city[i + 1] - 1];
	}
	return sum;
}

int exist(stack *path, int data)
{
	int i;
	for(i = 0 ; i < path->top ; i++)
	{
		if(path->city[i] == data)
		{
			return 1;
		}
	}
	return 0;
}

void travel()
{
	int i, sum;

 	if(min_path.top != 0 && (sum = sum_cost(&current_path)) > min_cost)
 	{
 		pop(&current_path);
 		return;
 	}

	if(current_path.top == N && city[current_path.city[N - 1] - 1][0] != 0)
	{
		sum = sum_cost(&current_path);
		sum += city[current_path.city[N - 1] - 1][0];
		if(sum < min_cost)
		{
			min_cost = sum;
			memcpy(&min_path, &current_path, sizeof(stack));
		}
	}
	else
	{
		for(i = 2 ; i <= N ; i++)
		{
			if(!exist(&current_path, i) && city[peek(&current_path) - 1][i - 1] != 0)
			{
				push(&current_path, i);
				travel();
			}
		}
	}
	pop(&current_path);
}