FIN

📌 문제 소개

중간 발표에서 수행하고자 하는 주제는 '어떻게 하면 쓰레기를 빨리 처리할 수 있을까?'에 대한 방법을 찾는 것이었다. 하단의 링크를 통해 중간 발표에서 했던 내용을 볼 수 있고, 이번 기말 발표의 주제도 같긴 하지만 접근 방법에서 약간의 수정을 하게 되었다.

https://velog.io/@minkyung2121/%EC%A4%91%EA%B0%84-%EB%B0%9C%ED%91%9C

하천 쓰레기 처리 관련한 기사를 찾다가 '하천으로 유입되는 쓰레기 중에 플라스틱, 비닐류 등은 자연환경에서 잘 분해되지 않아 하천뿐 아니라 해양 환경에 문제를 일으킨다'라는 문장을 읽게 되었다.

이것을 통해 내가 해결하고자 하는 문제는 위에 써놓은 주제와 같다. 부연 설명을 하자면 위도, 경도, 쓰레기의 종류를 알 수 있는 data csv 파일이 있다. 하나의 시작 지점을 정하여 다른 한 지점까지 도착하는 최단 경로를 구하는 것이 목표이다.

문제를 해결하기 위해 사용한 방법

1. 먼저 방문해야하는 노드를 정하여 알고리즘을 사용해 최적의 경로를 탐색한다.
2. 방문 순서를 저장하는 배열을 생성한 뒤, 방문 여부를 저장하는 배열을 생성하여 True/False로 확인한다.
3. 시작 노드로부터 노드를 거쳐서 가는 모든 노드를 탐색한다.
4. 방문하지 않은 노드를 탐색하고 끝났으면 처음 지점으로 돌아간다.
5. 탐색한 경로가 최단 경로일 때 값을 업데이트하고 순서와 방문 여부 배열에 값을 저장한다.

📌 데이터 소개

자료구조실습 수업을 듣는 화요일과 수요일 분반의 59개 데이터 csv 파일 중에서 나는 36명의 학생, 100개의 데이터를 사용하였다.

데이터 사용 방법

1. csv 파일 중 위도, 경도 값을 사용하여 거리 값을 구하는 공식에 대입
2. center(시작값)을 노원 자원회수 시설의 위도, 경도 값으로 지정한 후 point(점)과 center의 거리를 소수점 2번째 자리까지 나오도록 설정
3. 이를 통해 노원 자원회수 시설과 쓰레기 사진을 찍은 곳 사이의 거리를 알 수 있음

사이의 거리를 구하기 위해 작성한 distance.cpp 코드를 첨부하였다.
위도와 경도가 겹치는 데이터가 없게 하기 위하여 (중복값 방지) 모두 다른 데이터를 사용하였다. 소수점 둘째 자리까지 있는 데이터를 수집하면서 100개가 다 채워지지 않았기 때문에 본인의 데이터 정보를 사용한것도 있다.

#define _USE_MATH_DEFINES
#include <stdio.h>
#include "math.h"

class LatLong {
public:
    double latitude = 0;
    double longitude = 0;

    LatLong(double _lat, double _long) {
        latitude = _lat;
        longitude = _long;
    }
};

// return : KM
double calcDistance(LatLong start, LatLong end) {
    double distance = 0;

    double startLatitudeRadian = start.latitude * M_PI / 180;   // M_PI = 3.141592..
    double startLongitudeRadian = start.longitude * M_PI / 180;
    double endLatitudeRadian = end.latitude * M_PI / 180;
    double endLongitudeRadian = end.longitude * M_PI / 180;

    distance = acos(sin(startLatitudeRadian) * sin(endLatitudeRadian) + cos(startLatitudeRadian) * cos(endLatitudeRadian) * cos(endLongitudeRadian - startLongitudeRadian));

    distance = distance * 6371;

    return distance;
}

int main()
{
    LatLong center(37.64, 127.05); // 노원 자원회수 시설

    LatLong point1(37.49, 127.06); 
    LatLong point2(37.49, 127.07); 
    LatLong point3(37.50, 127.07); 
    LatLong point4(37.47, 127.07);  
    LatLong point5(37.51, 127.07);  
    LatLong point6(37.50, 127.06);  
    LatLong point7(37.52, 127.06);  
    LatLong point8(37.48, 127.05);  
    LatLong point9(37.52, 126.93);  
    LatLong point10(37.51, 127.06);  
    LatLong point11(37.48, 127.04);  
    LatLong point12(37.51, 127.08);  
    LatLong point13(37.52, 127.09);  
    LatLong point14(37.53, 126.92);  
    LatLong point15(37.58, 127.04);  
    LatLong point16(37.65, 127.01);  
    LatLong point17(37.59, 127.01);   
    LatLong point18(37.58, 127.01);   
    LatLong point19(37.54, 127.03);  
    LatLong point20(37.58, 127.01); 
    LatLong point21(37.59, 126.94); 
    LatLong point22(37.53, 126.88); 
    LatLong point23(37.54, 126.88); 
    LatLong point24(37.53, 126.89); 
    LatLong point25(37.52, 126.93); 
    LatLong point26(37.53, 126.93); 
    LatLong point27(37.51, 126.93); 
    LatLong point28(37.57, 126.90); 
    LatLong point29(37.57, 126.92); 
    LatLong point30(37.59, 127.02); 
    LatLong point31(37.52, 126.87); 
    LatLong point32(37.64, 127.11); 
    LatLong point33(37.31, 127.08); 
    LatLong point34(37.32, 127.08); 
    LatLong point35(37.59, 127.00); 
    LatLong point36(37.59, 127.10); 
    LatLong point37(37.58, 127.01); 
    LatLong point38(37.49, 127.11);  
    LatLong point39(37.49, 127.10);  
    LatLong point40(37.56, 127.00);  
    LatLong point41(37.51, 127.10); 
    LatLong point42(37.50, 127.10); 
    LatLong point43(37.50, 127.09); 
    LatLong point44(37.55, 126.90); 
    LatLong point45(37.52, 126.94); 
    LatLong point46(37.46, 126.83); 
    LatLong point47(37.46, 126.84); 
    LatLong point48(37.48, 126.90); 
    LatLong point49(37.31, 126.55); 
    LatLong point50(37.32, 126.55); 
    LatLong point51(37.48, 126.81); 
    LatLong point52(37.55, 126.88); 
    LatLong point53(37.56, 126.89); 
    LatLong point54(37.57, 126.86); 
    LatLong point55(37.57, 126.89); 
    LatLong point56(37.59, 126.75); 
    LatLong point57(37.59, 126.75); 
    LatLong point58(37.27, 127.46); 
    LatLong point59(36.98, 127.93); 
    LatLong point60(36.98, 127.94); 
    LatLong point61(36.97, 127.94); 
    LatLong point62(37.60, 127.01); 
    LatLong point63(37.66, 126.62); 
    LatLong point64(37.63, 126.54); 
    LatLong point65(37.70, 126.60); 
    LatLong point66(37.63, 126.70); 
    LatLong point67(37.43, 126.37); 
    LatLong point68(37.46, 127.09); 
    LatLong point69(37.53, 127.10); 
    LatLong point70(37.53, 127.22); 
    LatLong point71(37.56, 127.19); 
    LatLong point72(37.33, 127.11); 
    LatLong point73(37.53, 127.07); 
    LatLong point74(37.55, 127.22); 
    LatLong point75(37.67, 126.82); 
    LatLong point76(37.56, 127.18); 
    LatLong point77(38.19, 128.60); 
    LatLong point78(35.16, 129.14); 
    LatLong point79(37.49, 127.04); 
    LatLong point80(37.49, 126.98); 
    LatLong point81(37.47, 126.79); 
    LatLong point82(37.47, 126.80); 
    LatLong point83(37.56, 126.97); 
    LatLong point84(37.31, 126.54); 
    LatLong point85(37.35, 127.10); 
    LatLong point86(37.28, 126.55); 
    LatLong point87(37.29, 126.55); 
    LatLong point88(37.32, 127.10); 
    LatLong point89(37.49, 126.87); 
    LatLong point90(37.50, 126.87); 
    LatLong point91(37.60, 126.80); 
    LatLong point92(37.59, 126.80); 
    LatLong point93(37.00, 127.00); 
    LatLong point94(35.01, 127.00); 
    LatLong point95(37.67, 126.81); 
    LatLong point96(37.63, 126.92); 
    LatLong point97(37.63, 126.71); 
    LatLong point98(37.39, 126.46); 
    LatLong point99(37.39, 126.42); 
    LatLong point100(37.44, 126.43); 

    printf("point1: %.2f km\n", calcDistance(point1, center)); 
    printf("point2: %.2f km\n", calcDistance(point2, center));
    printf("point3: %.2f km\n", calcDistance(point3, center));
    printf("point4: %.2f km\n", calcDistance(point4, center));
    printf("point5: %.2f km\n", calcDistance(point5, center));
    printf("point6: %.2f km\n", calcDistance(point6, center));
    printf("point7: %.2f km\n", calcDistance(point7, center));
    printf("point8: %.2f km\n", calcDistance(point8, center));
    printf("point9: %.2f km\n", calcDistance(point9, center));
    printf("point10: %.2f km\n", calcDistance(point10, center));
    printf("point11: %.2f km\n", calcDistance(point11, center));
    printf("point12: %.2f km\n", calcDistance(point12, center));
    printf("point13: %.2f km\n", calcDistance(point13, center));
    printf("point14: %.2f km\n", calcDistance(point14, center));
    printf("point15: %.2f km\n", calcDistance(point15, center));
    printf("point16: %.2f km\n", calcDistance(point16, center));
    printf("point17: %.2f km\n", calcDistance(point17, center));
    printf("point18: %.2f km\n", calcDistance(point18, center));
    printf("point19: %.2f km\n", calcDistance(point19, center));
    printf("point20: %.2f km\n", calcDistance(point20, center));
    printf("point21: %.2f km\n", calcDistance(point21, center));
    printf("point22: %.2f km\n", calcDistance(point22, center));
    printf("point23: %.2f km\n", calcDistance(point23, center));
    printf("point24: %.2f km\n", calcDistance(point24, center));
    printf("point25: %.2f km\n", calcDistance(point25, center));
    printf("point26: %.2f km\n", calcDistance(point26, center));
    printf("point27: %.2f km\n", calcDistance(point27, center));
    printf("point28: %.2f km\n", calcDistance(point28, center));
    printf("point29: %.2f km\n", calcDistance(point29, center));
    printf("point30: %.2f km\n", calcDistance(point30, center));
    printf("point31: %.2f km\n", calcDistance(point31, center));
    printf("point32: %.2f km\n", calcDistance(point32, center));
    printf("point33: %.2f km\n", calcDistance(point33, center));
    printf("point34: %.2f km\n", calcDistance(point34, center));
    printf("point35: %.2f km\n", calcDistance(point35, center));
    printf("point36: %.2f km\n", calcDistance(point36, center));
    printf("point37: %.2f km\n", calcDistance(point37, center));
    printf("point38: %.2f km\n", calcDistance(point38, center));
    printf("point39: %.2f km\n", calcDistance(point39, center));
    printf("point40: %.2f km\n", calcDistance(point40, center));
    printf("point41: %.2f km\n", calcDistance(point41, center));
    printf("point42: %.2f km\n", calcDistance(point42, center));
    printf("point43: %.2f km\n", calcDistance(point43, center));
    printf("point44: %.2f km\n", calcDistance(point44, center));
    printf("point45: %.2f km\n", calcDistance(point45, center));
    printf("point46: %.2f km\n", calcDistance(point46, center));
    printf("point47: %.2f km\n", calcDistance(point47, center));
    printf("point48: %.2f km\n", calcDistance(point48, center));
    printf("point49: %.2f km\n", calcDistance(point49, center));
    printf("point50: %.2f km\n", calcDistance(point50, center));
    printf("point51: %.2f km\n", calcDistance(point51, center));
    printf("point52: %.2f km\n", calcDistance(point52, center));
    printf("point53: %.2f km\n", calcDistance(point53, center));
    printf("point54: %.2f km\n", calcDistance(point54, center));
    printf("point55: %.2f km\n", calcDistance(point55, center));
    printf("point56: %.2f km\n", calcDistance(point56, center));
    printf("point57: %.2f km\n", calcDistance(point57, center));
    printf("point58: %.2f km\n", calcDistance(point58, center));
    printf("point59: %.2f km\n", calcDistance(point59, center));
    printf("point60: %.2f km\n", calcDistance(point60, center));
    printf("point61: %.2f km\n", calcDistance(point61, center));
    printf("point62: %.2f km\n", calcDistance(point62, center));
    printf("point63: %.2f km\n", calcDistance(point63, center));
    printf("point64: %.2f km\n", calcDistance(point64, center));
    printf("point65: %.2f km\n", calcDistance(point65, center));
    printf("point66: %.2f km\n", calcDistance(point66, center));
    printf("point67: %.2f km\n", calcDistance(point67, center));
    printf("point68: %.2f km\n", calcDistance(point68, center));
    printf("point69: %.2f km\n", calcDistance(point69, center));
    printf("point70: %.2f km\n", calcDistance(point70, center));
    printf("point71: %.2f km\n", calcDistance(point71, center));
    printf("point72: %.2f km\n", calcDistance(point72, center));
    printf("point73: %.2f km\n", calcDistance(point73, center));
    printf("point74: %.2f km\n", calcDistance(point74, center));
    printf("point75: %.2f km\n", calcDistance(point75, center));
    printf("point76: %.2f km\n", calcDistance(point76, center));
    printf("point77: %.2f km\n", calcDistance(point77, center));
    printf("point78: %.2f km\n", calcDistance(point78, center));
    printf("point79: %.2f km\n", calcDistance(point79, center));
    printf("point80: %.2f km\n", calcDistance(point80, center));
    printf("point81: %.2f km\n", calcDistance(point81, center));
    printf("point82: %.2f km\n", calcDistance(point82, center));
    printf("point83: %.2f km\n", calcDistance(point83, center));
    printf("point84: %.2f km\n", calcDistance(point84, center));
    printf("point85: %.2f km\n", calcDistance(point85, center));
    printf("point86: %.2f km\n", calcDistance(point86, center));
    printf("point87: %.2f km\n", calcDistance(point87, center));
    printf("point88: %.2f km\n", calcDistance(point88, center));
    printf("point89: %.2f km\n", calcDistance(point89, center));
    printf("point90: %.2f km\n", calcDistance(point90, center));
    printf("point91: %.2f km\n", calcDistance(point91, center));
    printf("point92: %.2f km\n", calcDistance(point92, center));
    printf("point93: %.2f km\n", calcDistance(point93, center));
    printf("point94: %.2f km\n", calcDistance(point94, center));
    printf("point95: %.2f km\n", calcDistance(point95, center));
    printf("point96: %.2f km\n", calcDistance(point96, center));
    printf("point97: %.2f km\n", calcDistance(point97, center));
    printf("point98: %.2f km\n", calcDistance(point98, center));
    printf("point99: %.2f km\n", calcDistance(point99, center));
    printf("point100: %.2f km\n", calcDistance(point100, center));

    return 0;
}

distance를 구하고 이를 활용해서 다익스트라 알고리즘에 적용해야된다.
아래에 있는 코드는 main.cpp이며 간선들을 연결과 거리값을 부여하였다.

#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "math.h"
#include <type_traits>

#define MAX_NODE 100
#define INIT_VALUE 100000

typedef struct Typedef_Vertex
{
	int vertex;
	int distance;
	struct Typedef_Vertex* next;
}Typedef_Vertex;

typedef struct Typedef_Graph
{
	struct Typedef_Vertex* Adj_List[MAX_NODE];
}Typedef_Graph;

void AppendNode(Typedef_Graph*, int, int, int);
void DisplayGraph(Typedef_Graph);
void ShortestPath(Typedef_Graph, int, int);
void dijjkstra(Typedef_Graph, int, int);
void SearchPath(int, int);

void AppendNode(Typedef_Graph* g, int from, int to, int distance)
{
	if (from > MAX_NODE || to > MAX_NODE)
	{
		printf("ERROR: 잘못된 vertex 번호를 입력했습니다. \n\n");
		exit(-1);
	}

	Typedef_Vertex* v = (Typedef_Vertex*)malloc(sizeof(Typedef_Vertex));
	Typedef_Graph temp = *g;

	v->next = NULL;

	if (g->Adj_List[from] == NULL)
	{
		v->distance = distance;
		v->vertex = to;
		g->Adj_List[from] = v;
	}
	else
	{
		if (g->Adj_List[from]->distance > distance)
		{
			v->distance = distance;
			v->vertex = to;
			for (; temp.Adj_List[from]->next;
				temp.Adj_List[from] = temp.Adj_List[from]->next);

			temp.Adj_List[from]->next = v;
		}
	}
}

void DisplayGraph(Typedef_Graph graph)
{
	int i;
	Typedef_Graph g = graph;

	printf("\nfrom to\(distance_\n\n");

	for (i = 0; i < MAX_NODE; i++)
	{
		while (g.Adj_List[i] != NULL)
		{
			printf("%2d -> %2d", i, (g.Adj_List[1]->vertex));
			printf("\(%d\)\n", g.Adj_List[i]->distance);
			g.Adj_List[i] = g.Adj_List[1]->next;
		}
	}
	printf("\n\n");
}

const char* city[MAX_NODE] = { "n1", "n2", "n3", "n4", "n5", "n6", "n7" ... "n99", "n100"};
int Distance[MAX_NODE];
int path[MAX_NODE];

void ShortestPath(Typedef_Graph graph, int from, int to)
{
	int i;
	Typedef_Graph g = graph;

	if (from > MAX_NODE || to > MAX_NODE)
	{
		printf("ERROR: 잘못된 vertex 번호를 입력했습니다.\n\n");
		exit(-1);
	}

	for (i = 0; i < MAX_NODE;
		i++,
		Distance[i - 1] = INIT_VALUE,
		path[i - 1] = 1);

	Distance[from] = 0;

	dijkstra(g, from, to);
	printf("*** %s에서 %s까지 ***\n\n", city[from], city[to]);

	if (Distance[to] != INIT_VALUE)
	{
		printf("1. %-15s \[%d]\n", "D I S T A N C E", Distance[to]);
		SearchPath(from, to);
	}
	else
	{
		printf("경로 없음\n");
	}
}

typedef struct QueueData
{
	int value;
	struct QueueData* NEXT;
}QueueData;

QueueData* Create_Queue();
void init(QueueData* Q);
void enqueue(QueueData** Q, int Value);
int dequeue(QueueData** Q);
void Delete_Queue(QueueData** Q);
void Is_Empty(QueueData** Q);
int printf();

QueueData* Create_Queue()
{
	QueueData* Start = NULL;
	Start = malloc(sizeof(QueueData));
	init(Start);
	return Start;
}

void init(QueueData* Q)
{
	Q->value = NULL;
	Q->NEXT = NULL;
}

void enqueue(QueueData** Q, int Value)
{
	if ((*Q)->value != NULL)
	{
		QueueData* Temp = malloc(sizeof(QueueData));
		init(Temp);

		Temp->value = Value;
		Temp->NEXT = (*Q);
		(*Q) = Temp;
	}
	else
	{
		(*Q)->value = alue;
	}
}

void Print_Queue(QueueData* Q)
{
	QueueData* Temp;
	Temp = Q;

	if (Temp == NULL)
	{
		printf("Queue is empty\n");
	}
	else
	{
		while (Temp != NULL)
		{
			printf("%d ", Temp->value);
			Temp = Temp->NEXT;
		}
		printf("\n ");
	}
}

int dequeue(QueueData** Q)
{
	int returnValue;

	QueueData* Temp = (*Q);
	QueueData* NewTail = (*Q);

	if ((*Q)->NEXT == NULL)
	{
		returnValue = (*Q)->value;
		free((*Q));
		(*Q) = NULL;
	}
	else
	{
		while(Temp->NEXT != NULL)
		{
			NewTail = Temp;
			Temp = Temp->NEXT;
		}
		returnValue = Temp->value;
		free(Temp);

		NewTail->NEXT = NULL;
	}

	return returnValue;
}

void Delete_Queue(QueueData** Q)
{
	QueueData* Temp = *Q;

	while (*Q != NULL)
	{
		QueueData* Temp = (*Q);
		QueueData* NewTail = (*Q);

		if ((*Q)->NEXT == NULL)
		{
			free((*Q));
			(*Q) = NULL;
		}
		else
		{
			while (Temp->NEXT != NULL)
			{
				NewTail = Temp;
				Temp = Temp->NEXT;
			}
			free(Temp);

			NewTail->NEXT = NULL;
		}
	}
}

void is_empty(QueueData** Q)
{
	if ((*Q) == NULL)
		printf("Queue is empty\n");
	else
		printf("Queue is not empty\n");
}

void dijkstra(Typedef_Graph graph, int from, int to)
{
	int i = 0;

	enqueue(from);
	Typedef_Graph g = graph;

	while (!is_empty())
	{
		from = dequeue();

		for (; g.Adj_List[from]; g.Adj_List[from] = g.Adj_List[from]->next)
		{
			if (Distance[g.Adj_List[from]->vertex] 
					> g.Adj_List[from]->distance + Distance[from])
			{
				Distance[g.Adj_List[from]->vertex] =
					g.Adj_List[from]->distance + Distance[from];
			
				path[g.Adj_List[from]->vertex] = from;
				enqueue(g.Adj_List[from]->vertex);
			}
		}
	}
}

void SearchPath(int from, int to)
{
	int vertex = to;
	int stack[MAX_NODE];
	int Top = 0;

	stack[Top++] = vertex;

	while (1)
	{
		vertex = path[vertex];
		stack[Top++] = vertex;
		if (vertex == from) break;
	}

	printf("2. %-15s: ", "P A T H");
	while (--Top >= 0) {
		printf("\[%s]\ ", city[stack[Top]]);
		if (Top > 0) { printf("->"); }
	}
	printf("\n\n");
}

class LatLong {
public:
	double latitude = 0;
	double longitude = 0;

	LatLong(double _lat, double _long) {
		latitude = _lat;
		longitude = _long;
	}
};

int main()
{
	Typedef_Graph graph;
	int i;

	for (i = 0; i < MAX_NODE; i++, graph.Adj_List[i - 1] = NULL);

	AppendNode(&graph, 1, 0, 16.7);
	AppendNode(&graph, 2, 0, 16.77);
	AppendNode(&graph, 2, 1, 15.67);
	AppendNode(&graph, 3, 2, 18.99);
	AppendNode(&graph, 4, 3, 14.56);
	AppendNode(&graph, 4, 5, 15.59);
	AppendNode(&graph, 5, 3, 13.37);
	AppendNode(&graph, 5, 6, 17.79);
	AppendNode(&graph, 5, 7, 17.03);
	AppendNode(&graph, 6, 7, 14.48);
	AppendNode(&graph, 7, 0, 17.81);
					.
                    .
                    .
    AppendNode(&graph, 98, 99. 62.13);
    AppendNode(&graph, 98, 100, 59.02);
    
	DisplayGraph(graph);

	ShortestPath(graph, 4, 0);

	return 0;
}

📌 결과 및 효과

유형 효과와 무형 효과로 나눌 수 있다. 먼저 유형 효과는 명확한 금전적 이익으로 환산되는 효과를 뜻하고 무형 효과는 이와 반대로 잠재적인 이익이 되는 당분간은 비금전적인 표과를 말한다.

3-1. 유형 효과

· 쓰레기 처리 시간 단축

쓰레기를 직접 수거하는 것이 아닌 최단 경로를 통해 가기 때문에 직접 수거하는 것보다 낭비되는 처리 시간을 단축할 수 있다.

· 원가 절감

시간이 단축됨에 따라 비용도 같이 단축되는 효과가 있다.

· 비즈니스 효과

현재 도봉구에서 인공지능 폐기물을 선별하는 로봇을 사용하고 있다. 최단경로를 사용하여 쓰레기를 처리하는 것과 기술을 합치면 더 좋은 결과물을 통해 비스니스 효과를 얻을 수 있다.

3-2. 무형 효과

· 기술적 경쟁우위

'하천 쓰레기 처리'의 문제점에 대해 다루는 경우가 적다. 프로젝트의 결과물을 통해 기술에 대한 경쟁력이 생긴다.

·지적 자산 활용빈도 증대

무형적인 것으로서 재산적 가치가 실현될 수 있는 지적창작물에 부여된 재산에 대한 권리를 말한다. 새로운 기술을 사용하여 활용하는 횟수가 늘어난다.

· 개선 활동 시스템 구축

쓰레기를 한번에 처리하기 힘들다는 문제점이 있을 때 시스템을 구축하면 문제 해결에 도움이 된다.