크루스칼 알고리즘_고속도로 길찾기 [1/1]

뭔가 했더니 도시 간 고속도로를 최단 거리로 잇기 위해서는 어떻게 할 것이냐하는 옛 퀴즈를 푸는 알고리즘입니다. 아래와 같이 각 도시 간 이어진 고속도로가 있고 최단거리로 모든 도시를 한바퀴 돌려면 어디서 출발해서 어느 길로 가야하는가를 푸는 문제라고 보면 되겠네요. 실전에서는 어디다가 쓰이는지는 감이 잘 안잡히지만 일단 한 번 풀어보겠습니다.

 

 

---

 

먼저 두 가지 기준이 생각났는데 첫 번째로는 도시를 기준으로 연결돼 있는 길들을 잇는 방식입니다. 하지만 이 방식은 도시 - 도시 간 최단거리는 찾을 수 있겠지만 전체로 볼 때 가장 짧은 루트를 찾을 수는 없으므로 패스하겠습니다.

​

그럼 각 길을 중심으로 찾는 방법이 있겠네요. 보자마자 떠오른 방식은 연결리스트를 응용하는 것인데 잘 될지 한 번 짜보겠습니다. 전체 코드는 제일 하단에 있습니다.

 

 

---

 

[ int main() ]

• 도로 정보 입력(함수), 도시 정보 입력(함수), 도로 정렬(힙정렬 함수)
• 포인터 배열로 썼지만 이미 데이터 사이즈가 정해져있기 때문에 일반 구조체 배열로 써도 무방
• 다만, 일반 구조체 배열을 쓸 경우 정렬 함수 수행 시 메모리 사용이 매우 비효율적
• 연결리스트의 head를 찾는 함수를 사용해서 루핑(돌고 도는 구조)을 방지
• 같은 연결 리스트에 속한 그룹(같은 head를 가진 그룹) 이라면 연결하지 않음
• 도로는 거리가 적은 도로부터 순서대로 찾아나감

 

※ Point (삼항연산자(3항연산자) 사용)
- if 절을 간단하게 줄일 수 있는 문법
          [ 조건 ? (True경우 수행할 내용) : (False일 경우 수행할 내용); ]
- 여러 개 변수값을 변경해줘야할 때
          [ 조건 ? (변수1 = x) : (변수2 = y); ]
- 하나의 변수에만 값을 넣어주면 될 때 (삼항연산부터 수행한 뒤, 값을 변수에 넣어줌)
          [ 변수 = 조건 ? (값1) : (값2); ]

#include <stdio.h>
#include <stdlib.h>
# define HIGHWAY_SIZE 12
# define CITY_SIZE 7

typedef struct highway {
	int c1;  // 도시 이름 1
	int c2;  // 도시 이름 2
	int dist;  // 고속도로 거리
}high;

typedef struct node {
	int city;  // 현재 도시
	int next;  // 상위 도시
}city;

void arrange_highway(high* h[]);
void swap(high* h[], int x, int y);
int input_highway(high* h[]);
int input_city(city* c[]);
int find_head(city* c[], int city);

int main()
{
	high* h[HIGHWAY_SIZE] = { NULL };  // 고속도로 정보
	high* selected_h[CITY_SIZE - 1] = { NULL };  // 최종 선택된 고속도로
	city* c[CITY_SIZE] = { NULL };  // 도시 정보

	if (input_highway(h) == 1)  // 고속도로 정보 생성
		return 1;
	if (input_city(c) == 1)  // 도시 정보 생성
		return 1;
	arrange_highway(h);  // 고속도로 거리순으로 정렬

	/* 최적 고속도로 구성 찾기 (도로 수는 도시 수보다 1 적음) */
	for (int i = 0, j = 0; i < HIGHWAY_SIZE && j < CITY_SIZE - 1; i++)
	{
		/* 비어있는 h[i]는 없지만 비주얼 스튜디오 warning 없애기 */
		if (h[i] == NULL)	
			break;
		/* 연결돼 있지 않은 경우 연결 (같은 루트를 넣어줌) */
		int head1 = find_head(c, h[i]->c1), head2 = find_head(c, h[i]->c2);
		if (head1 != head2)
		{
			/* 더 작은 루트를 가진 쪽으로 연결 */
			head1 > head2 ? 
				(c[h[i]->c1]->next = h[i]->c2) : (c[h[i]->c2]->next = h[i]->c1);
			selected_h[j++] = h[i];
		}
	}

	/* 도로 결과 출력 (도로 수는 도시 수보다 1 작음) */
	int sum = 0;
	printf("\n");
	for (int i = 0; i < CITY_SIZE - 1; i++)
	{
		if (c[i] == NULL)	// warning 방지용
			break;
		printf(" 도시1 : %d, 도시2 : %d, 거리 : %d\n", selected_h[i]->c1, 
			selected_h[i]->c2, selected_h[i]->dist);
		sum += selected_h[i]->dist;
	}
	printf(" - 거리 합계 : %d\n\n", sum);

	/* 도시 간 연결 정보 */
	for (int i = 0; i < CITY_SIZE; i++)
	{
		if (c[i] == NULL)
			break;
		printf(" 하위도시 : %d, 상위도시 : %d\n", c[i]->city, c[i]->next);
	}
}

 

---

 

[ arrange_highway() - 입력된 고속도로 정보 힙정렬(오름차순) ]

• 힙정렬과 동일, 포인터 배열을 쓰지 않을 경우 정렬 시에 메모리가 비효율적으로 사용됨

/* 고속도로 거리정보 힙정렬 (짧은 거리순 오름차순) */
/* parameter : 고속도로 정보 포인터 배열 */
/* return : void */
void arrange_highway(high* h[])
{
	/* 힙트리 생성 */
	for (int i = 1; i < HIGHWAY_SIZE; i++)
	{
		int c = i;
		while (c > 0)
		{
			int p = (c - 1) / 2;
			if (h[c]->dist > h[p]->dist)
			{
				swap(h, c, p);
				c = p;
			}			
			else break;
		}
	}
	swap(h, 0, HIGHWAY_SIZE - 1);

	/* 힙 정렬 수행 */
	for (int size = HIGHWAY_SIZE - 1; size > 1; size--)
	{
		int p = 0;
		while (p < size / 2)
		{
			int c = p * 2 + 1;
			if (c + 1 < size && h[c]->dist < h[c + 1]->dist)
				c++;
			if (h[p]->dist < h[c]->dist)
				swap(h, p, c);
			else
				break;
			p = c;
		}
		swap(h, 0, size - 1);
	}
}

/* swap */
void swap(high* h[], int x, int y)
{
	high* temp = h[x];
	h[x] = h[y];
	h[y] = temp;
}

 

---

 

[ input_highway(), input_city() - 도로, 도시 정보 입력 ]

• 막 때려넣고 한 번에 집어넣는게 편함, 코드도 짧아짐

/* 도로 정보 입력 */
/* parameter : high 타입 포인터 배열 */
/* return : 정상 == 0, 비정상 == 1 */
int input_highway(high* h[])
{
	/* 길 정보 */
	int temp[][3] = { {0,2,15},{0,1,10},{1,2,22},{0,6,50},
	{1,6,18},{2,6,11},{1,5,28},{5,6,25},{6,3,32},{3,4,41},{2,4,8},{5,3,29} };

	/* 정보 입력 */
	for (int i = 0; i < HIGHWAY_SIZE; i++)
	{
		if ((h[i] = (high*)malloc(sizeof(high))) == NULL)
			return 1;
		int j = 0;
		h[i]->c1 = temp[i][j];
		h[i]->c2 = temp[i][++j];
		h[i]->dist = temp[i][++j];
	}
	return 0;
}


/* 도시 정보 입력 */
/* parameter : city 타입 포인터 배열 */
/* return : 정상 == 0, 비정상 == 1 */
int input_city(city* c[])
{
	for (int i = 0; i < CITY_SIZE; i++)
	{
		if ((c[i] = (city*)malloc(sizeof(city))) == NULL)
			return 1;
		c[i]->city = i;
		c[i]->next = i;	 // 기본값은 자기 자신
	}
	return 0;
}

 

---

 

[ find_head() - 연결리스트의 head를 찾음 ]

• 도로정보에 있는 두 도시를 비교할 때, head값이 같은지 비교해줘야 함
• next가 int형인 것을 빼면 연결리스트 head 찾기와 동일

/* 루트의 루트가 바꼈을 때, 하위 도시들의 루트도 같이 바꿔줌 */
/* parameter : city 타입 포인터 배열, 도시이름 */
/* return : 루트(head)도시 이름 */
int find_head(city* c[], int i)
{
	while (c[i]->city != c[i]->next)
		i = c[i]->next;
	return i;
}

 

---

 

[ 전체 코드 ]

#include <stdio.h>
#include <stdlib.h>
# define HIGHWAY_SIZE 12
# define CITY_SIZE 7

typedef struct highway {
	int c1;  // 도시 이름 1
	int c2;  // 도시 이름 2
	int dist;  // 고속도로 거리
}high;

typedef struct node {
	int city;  // 현재 도시
	int next;  // 상위 도시
}city;

void arrange_highway(high* h[]);
void swap(high* h[], int x, int y);
int input_highway(high* h[]);
int input_city(city* c[]);
int find_head(city* c[], int city);

int main()
{
	high* h[HIGHWAY_SIZE] = { NULL };  // 고속도로 정보
	high* selected_h[CITY_SIZE - 1] = { NULL };  // 최종 선택된 고속도로
	city* c[CITY_SIZE] = { NULL };  // 도시 정보

	if (input_highway(h) == 1)  // 고속도로 정보 생성
		return 1;
	if (input_city(c) == 1)  // 도시 정보 생성
		return 1;
	arrange_highway(h);  // 고속도로 거리순으로 정렬

	/* 최적 고속도로 구성 찾기 (도로 수는 도시 수보다 1 적음) */
	for (int i = 0, j = 0; i < HIGHWAY_SIZE && j < CITY_SIZE - 1; i++)
	{
		/* 비어있는 h[i]는 없지만 비주얼 스튜디오 warning 없애기 */
		if (h[i] == NULL)	
			break;
		/* 연결돼 있지 않은 경우 연결 (같은 루트를 넣어줌) */
		int head1 = find_head(c, h[i]->c1), head2 = find_head(c, h[i]->c2);
		if (head1 != head2)
		{
			/* 더 작은 루트를 가진 쪽으로 연결 */
			head1 > head2 ? 
				(c[h[i]->c1]->next = h[i]->c2) : (c[h[i]->c2]->next = h[i]->c1);
			selected_h[j++] = h[i];
		}
	}

	/* 도로 결과 출력 (도로 수는 도시 수보다 1 작음) */
	int sum = 0;
	printf("\n");
	for (int i = 0; i < CITY_SIZE - 1; i++)
	{
		if (c[i] == NULL)	// warning 방지용
			break;
		printf(" 도시1 : %d, 도시2 : %d, 거리 : %d\n", selected_h[i]->c1, 
			selected_h[i]->c2, selected_h[i]->dist);
		sum += selected_h[i]->dist;
	}
	printf(" - 거리 합계 : %d\n\n", sum);

	/* 도시 간 연결 정보 */
	for (int i = 0; i < CITY_SIZE; i++)
	{
		if (c[i] == NULL)
			break;
		printf(" 하위도시 : %d, 상위도시 : %d\n", c[i]->city, c[i]->next);
	}
}

/* 고속도로 거리정보 힙정렬 (짧은 거리순 오름차순) */
/* parameter : 고속도로 정보 포인터 배열 */
/* return : void */
void arrange_highway(high* h[])
{
	/* 힙트리 생성 */
	for (int i = 1; i < HIGHWAY_SIZE; i++)
	{
		int c = i;
		while (c > 0)
		{
			int p = (c - 1) / 2;
			if (h[c]->dist > h[p]->dist)
			{
				swap(h, c, p);
				c = p;
			}			
			else break;
		}
	}
	swap(h, 0, HIGHWAY_SIZE - 1);

	/* 힙 정렬 수행 */
	for (int size = HIGHWAY_SIZE - 1; size > 1; size--)
	{
		int p = 0;
		while (p < size / 2)
		{
			int c = p * 2 + 1;
			if (c + 1 < size && h[c]->dist < h[c + 1]->dist)
				c++;
			if (h[p]->dist < h[c]->dist)
				swap(h, p, c);
			else
				break;
			p = c;
		}
		swap(h, 0, size - 1);
	}
}

/* swap */
void swap(high* h[], int x, int y)
{
	high* temp = h[x];
	h[x] = h[y];
	h[y] = temp;
}


/* 도로 정보 입력 */
/* parameter : high 타입 포인터 배열 */
/* return : 정상 == 0, 비정상 == 1 */
int input_highway(high* h[])
{
	/* 길 정보 */
	int temp[][3] = { {0,2,15},{0,1,10},{1,2,22},{0,6,50},
	{1,6,18},{2,6,11},{1,5,28},{5,6,25},{6,3,32},{3,4,41},{2,4,8},{5,3,29} };

	/* 정보 입력 */
	for (int i = 0; i < HIGHWAY_SIZE; i++)
	{
		if ((h[i] = (high*)malloc(sizeof(high))) == NULL)
			return 1;
		int j = 0;
		h[i]->c1 = temp[i][j];
		h[i]->c2 = temp[i][++j];
		h[i]->dist = temp[i][++j];
	}
	return 0;
}


/* 도시 정보 입력 */
/* parameter : city 타입 포인터 배열 */
/* return : 정상 == 0, 비정상 == 1 */
int input_city(city* c[])
{
	for (int i = 0; i < CITY_SIZE; i++)
	{
		if ((c[i] = (city*)malloc(sizeof(city))) == NULL)
			return 1;
		c[i]->city = i;
		c[i]->next = i;  // 기본값은 자기 자신
	}
	return 0;
}


/* 루트의 루트가 바꼈을 때, 하위 도시들의 루트도 같이 바꿔줌 */
/* parameter : city 타입 포인터 배열, 도시이름 */
/* return : 루트(head)도시 이름 */
int find_head(city* c[], int i)
{
	while (c[i]->city != c[i]->next)
		i = c[i]->next;
	return i;
}

 

---

 

강의 듣고 왔는데 C++로 하셔서 강의 코드는 따로 없습니다. 전 JAVA로 넘어갈 생각이라..

본 과제는 유투브 '동빈나'님의 알고리즘 강의를 참고하였습니다.