부유쓰레기 수거
문제
문제소개
수정이는 해양 쓰레기를 수집하기 위해 20개의 부유쓰레기 데이터를 모았다.
수정이가 수집한 데이터의 따르면, 20개의 데이터는 위치정보(장소명, 위도, 경도)와 분류정보(플라스틱 등)가 포함되어 있으며 해당 정보들은 다른 데이터와 겹치지 않는다.
쓰레기를 수거하기 위한 인력 비용은 최저시급 1만원 + 위험근무수당 4만원으로 5만원이 든다. 수정이는 비용을 줄이기 위해 해양로봇을 만들어 단돈 1만원으로 수거한다. (한 지점당)
모은 데이터 정보를 로봇에 입력해 모든 지점에 방문하여 쓰레기를 수거하고자 한다.
로봇의 시작지점은 수집 데이터 중 수정이의 본가인 서울식물원 호수공원으로 한다.
로봇은 최소한의 비용을 위해 최단거리로 이동한다.(수정이는 학생이라 금전이 부족하다!)
문제풀이
모든 장소에 방문하여 쓰레기를 수거해야 하는 만큼, 다익스트라 알고리즘을 이용하여 문제를 해결하도록 한다.
다익스트라 알고리즘은 모든 정점과 정점 사이의 최소의 가중치로 연결되어야 하며 음의 가중치가 포함되지 않아야 한다는 특징을 가지고 있다.
- 정점 : 한 장소를 하나의 정점으로 하여 총 20개의 정점으로 이루어져 있다.
- 가중치 : 두 정점 간의 위도 경도 차를 이용해 실제 거리 계산으로 가중치를 반영한다.
문제코드
// Dijkstra알고리즘의 최단 경로 탐색 기능이 추가된 그래프
class WGraphDijkstra : public WGraph {
int dist[MAX_VTXS]; // 시작노드로부터의 최단경로 거리
bool found[MAX_VTXS]; // 방문한 정점 표시 → 집합 S
public:
int chooseVertex() { // 가장 비용 적은 미방문 정점을 반환
int min = INF;
int minpos = -1;
for( int i=0 ; i<size ; i++ )
if( dist[i]< min && !found[i] ){
min = dist[i];
minpos = i;
}
return minpos;
}
void printDistance() { //모든 정점들의 dist[] 값 출력
for( int i=0 ; i<size ; i++)
printf("%5d", dist[i]);
printf("\n");
}
// Dijkstra의 최단 경로 알고리즘: start 정점에서 시작함.
void ShortestPath( int start ) {
for( int i=0 ; i<size ; i++) { //초기화: dist[], found[]
dist[i] = getEdge(start,i); //인접행렬 값 반환(간선 가중치)
found[i] = false; //처음에 S집합은 비어있음.
}
found[start] = true; // S에 포함
dist[start] = 0; // 최초 거리
for( int i=0 ; i<size ; i++ ){
printf("Step%2d:", i+1);
printDistance(); // 모든 dist[] 배열값 출력
int u = chooseVertex(); // S에 속하지 않은 비용 가장 작은 정점 반환
found[u] = true; // 집합 S에 포함
for( int w=0 ; w<size ; w++) {
if( found[w] == false )//S에 속하지 않는 노드 w의 dist값 갱신
if( dist[u] + getEdge(u,w) < dist[w] )
dist[w] = dist[u] + getEdge(u,w);
} // u를 거쳐가는 것이 최단 거리이면 dist[] 갱신
}
}
};
void load(char* filename){
ifstream fp(filename);
if (fp.is_open())
{
int n, val;
fp >> n;
for (int i = 0; i < n; i++) { // number of vertices
char str[80];
fp >> str; // vertex
insertVertex(str[0]);
for (int j = 0; j < n; j++) {
fp >> val; // edge
if (i>j && val != 0) insertEdge(i, j);
}
}
}
else cout << "File can not be found !" << endl;
}
데이터
사용데이터 정제
- 본인을 포함한 13명의 학우들의 데이터를 사용
- 위치 정보가 겹치지 않는 데이터를 선정
- 부유 쓰레기의 종류 정보를 한 장소당 임의로 하나의 데이터 선정
- 종류가 다양하도록 부족한 데이터는 본인 데이터 추가
(본인 데이터는 유리와 캔의 데이터를 많이 가지고 있음)
- 데이터를 수집하여 엑셀 파일로 저장함
- 데이터 넘버링, 학우의 이름, 장소명, 데이터의 크기(가로, 세로), 데이터의 위치정보(위도, 경도), 데이터의 종류 순으로 나열
- 코드에서 쉼표(,)로 읽을 수 있도록 CSV파일로 저장함
분류종류
- Rubbish, Plastics, Cans, Glass, Papers의 5개의 카테고리를 고르게 반영함
- Rubbish(4), Plastics(6), Cans(4), Glass(3), Papers(3)
정점정보
- 서울식물원 호수공원, 강서습지생태공원, 성북천, 석촌호수, 안양천, 홍제천, 대명항, 탄천, 청계천, 양재천, 중랑천, 뚝섬유원지, 충주금곡소류지, 통복천, 묵동천, 불암천, 불광천, 창원천, 성복천 으로 총 20곳을 선정함
- 각 장소의 위치정보(위도, 경도)는 소수점 아래 3자리까지만 반영
- 2자리인 경우 마지막 0이 생략됨(해당 부분은 수정해서 CSV에 반영하였음)
간선정보
PPT 추가사항 => 가중치 여부 반영
20곳의 위치를 실제 물길을 반영하여 간선의 여부를 나타남
실제 군문교와 통복천, 창원천은 물길이 이어지지 않아 이동이 불가능함
PPT 추가사항 => 가중치 여부 및 값 반영
간선 여부에 따라서 정점간의 거리를 위도, 경도 차로 구함
위도간의 차의 제곱과 경도간의 차의 제곱을 더한 값에 루트를 씌워준다.
가중치 = √ ( (위도 차)^2 + (경도 차)^2 )
EX) 0.021(생략) = √( (0.016)^2 + (0.014)^2 )
해당 결과의 소수점 2번째까지만 반영하여 100을 곱해준 값을 가중치로 한다.
EX) 0.02 * 100 = 2
효과
유형효과
해양로봇을 이용해 육지를 통한 수거에 비해 단축된 거리로 쓰레기를 쉽게 수거해 거리 비례 비용이 절감된다.
해당 문제에서 제시된 인력 비용의 경우 : 5만원 x 20곳 => 100만원
해양 로봇을 이용한 부유쓰레기 수거 비용 : 1만원 x 20곳 => 20만원
80만원의 손실을 막을 수 있다.
무형효과
- 전국 하천 및 저수지, 생태공원의 이미지 개선
- 생활 쓰레기로 인한 오수 발생 감소
- 부유 쓰레기의 바다 유입량 감소
