꿈을 꾸다...

/* 

Subject: #140 Bandwidth

e-mail: morcavon@gmail.com

Homepage: http://www.morcavon.com

Building: 14/04/2005 ~ 14/04/2005

Last Update: 14/04/2005

*/



/*

<INPUT>

node:neighbours;.......

...

#

-

<OUTPUT>

A B C D..... -> bandwidth

-

<CONDITION>

Write a program that will find the ordering of a graph that minimised the bandwidth.

A node name is a single upper case character in the range 'A' to 'Z'.

# of nodes <= 8

*/



#include <iostream>

using namespace std;

#include <cstring>







typedef struct Node* pNode;

struct Node

{

	char name; // node's name(single upper case A to Z)

	pNode link; // link to node's neighbours

};





void init(Node node[]);

void perm(char *var, const short k, const short n);







short maxi = 0, mini = 8;

char result[9];

Node node[8] = {NULL};



int main()

{

	pNode w_ptr = node; // current node

	pNode t_ptr;

	short i, n;

	char ch;

	char mask[26] = {0}, ordering[8];



	while (1) {



		//////////////////////////////////////////////////////////////////////////

		/////////////////////////// INPUT PART /////////////////////////////////

		//////////////////////////////////////////////////////////////////////////

		cin.get(ch);

		if (ch == '#') // termination character

			break;

		else if (ch == '\n') {

			// 한 줄 입력 끝. 

			//////////////////////////////////////////////////////////////////////////

			/////////////////////////// OUPUT PART /////////////////////////////////

			//////////////////////////////////////////////////////////////////////////

			// 기본 순열 생성

			for (n = i = 0; i < 26; i++) {

				if (mask[i])

					ordering[n++] = i + 'A';

			}



			// 알파벳순으로 순열을 만들면서 최소 bandwidth를 찾는다.

			perm(ordering, 0, n);

			for (i = 0; i < n; i++) {

				cout << result[i] << ' ';

			}

			cout << "-> " << mini << endl;





			// reseting

			maxi = 0;

			mini = 8;

			memset(mask, 0, 26);

			w_ptr = node;

			init(node);

			continue;

		}





		if (ch == ';') {

			w_ptr++;

		}

		else if (ch >= 'A' && ch <= 'Z') {

			// 입력시에 나타나는 값들을 표시해 두자

			mask[ch - 'A'] = 1;



			if (w_ptr->name == 0) {

				// new node

				w_ptr->name = ch;

			}

			else {

				// add neightbour to node

				t_ptr = w_ptr->link;

				w_ptr->link = new Node;

				w_ptr->link->name = ch;

				w_ptr->link->link = t_ptr;

			}

		} // end of input

	}



	return 0;

}









void init(Node node[])

{

	pNode temp;



	for (short i = 0; i < 8; i++) {

		while (node[i].link != NULL) {

			temp = (node[i].link)->link;

			delete node[i].link;

			node[i].link = temp;

		}



		node[i].name = 0;

	}

}









short idxInOrdering(char ch, char ordering[])

{

	// ordering에서 ch가 몇번째 위치에 있는지 리턴

	short i = 0;

	while (ch != ordering[i])

		i++;



	return i;

}







short findMax(char var[], short n)

{

	// var 순열에서 최대 bandwidth를 찾는다.

	short t_max = 0;

	pNode w_ptr = node;

	short i, x, y;



	for (i = 0; node[i].name != 0; i++) {

		w_ptr = &node[i];

		x = idxInOrdering(w_ptr->name, var);



		while (w_ptr->link) {

			y = idxInOrdering(w_ptr->link->name, var);

			if (abs(x - y) > t_max)

				t_max = abs(x - y);

			w_ptr = w_ptr->link;

		}

	}



	return t_max;

}







void perm(char *var, const short k, const short n)

{

	// var[k] ~ var[n-1]에 대한 순열 생성.

	short i;



	if (k == n - 1) {

		// 정해진 순열에서 최대값의 최소값을 추적...

		if (mini > (maxi = findMax(var, n))) {

			mini = maxi;

			strncpy(result, var, n);

			result[n] = '\0';

		}

	}

	else {

		for (i = k; i < n; i++) {

			// var[k]와 var[i]를 교환

			char temp = var[k]; var[k] = var[i]; var[i] = temp;

			perm(var, k + 1, n);

			// 복원

			temp = var[k]; var[k] = var[i]; var[i] = temp;

		}

	}

}