최단 경로 찾기 SDK
👀 Overview
| 한줄 소개 | N개의 지점에 대한 최단 경로를 찾아주는 Sdk |
| 진행기간 | 2022.02.02 ~ 진행중 |
| Skills | Gson, Retrofit2, Service Component, Naver Map SDK |
| 팀구성 | Android 1 |
❓ 개발 의도 및 개발 목표
기획 의도
- 안드로이드를 처음 학습하고 개인적인 실습을 위한 토이 프로젝트
- 배달 라이더 분들이 여러 집을 방문하면서 최단 경로를 찾아주는 앱이 없음
- 이에 대한 해결책으로 구상
개발 목표
해당 프로젝트는 아래의 내용을 증명하는 것을 목표로 함.
- 안드로이드 학습에 있어 새로 배운 내용들을 적용하고 내 것으로 만들고자 함
- Map SDK를 적용하며 Map 콜백에 대한 이해
🍀 서비스 내용
좌표 리스트를 담아서 함수에 담으면 최단 경로로 리스트들을 정렬해서 반환해 줍니다.
이 library를 이용한 앱에서는 좌표를 찍어 마커와 바텀시트로 데이터를 저장 및 표시해주며, 탐색을 시작하면 최단 경로로 경로를 표시해 줍니다.
🛠 기술 스택
- Retrofit2
- Naver Api를 통해 좌표에 대한 주소 정보 또는 주소를 통한 좌표 정보를 가져올 수 있도록 함
- Gson
- 네트워크 통신 시 받아오는 데이터를 Gson으로 데이터를 파싱
- Service Component
- TSP 계산 비동기 처리를 위해 사용
- TSP 알고리즘은 매우 오래걸리는 작업이며, 이를 비동기 처리를 위해 사용
- 이는 Service에 대한 학습을 위해 사용하게 되었음
- Naver Map SDK
- Naver Map을 통해 마커 표시와 지도 표시를 해주며, 경로를 표현해 준다.
- TSP 알고리즘
- 이 서비스의 중심인 알고리즘
- 외판원 순회 문제를 토대로 library에 이를 적용하여 앱에서 사용한다.
🖥 개발 내용
FindShortestPath Library
FindShortestPath 클래스의 수행 순서는 다음과 같습니다.
- 좌표를 사용자에게서 받아온다.
- Naver Api를 통해 각 좌표간의 거리를 계산해 n x n Board를 만든다.
- 이 Board를 기반으로 TSP클래스를 통해 가장 짧은 거리를 계산한다.
이 클래스는 쓰레드를 상속받아 워커 쓰레드로 사용자의 동작과 비동기적으로 수행하게끔 만들었으며, 각 단계마다 리스너를 통해 성공했음을 콜백으로 알려줍니다.
TSP Class
외판원 순회 문제를 인용해 해당 알고리즘을 적용했습니다.
참고했던 백준 문제는 2098번이며 적용했던 알고리즘에 대한 기술은 향후 수정하겠습니다.
📈 성장 경험
- 안드로이드 처음 공부할 때 익숙해질 겸 개발한것이라 리팩토링에 큰 어려움을 겪고 있음
- 사실상 처음부터 개발하고 있는 중
- TSP 알고리즘의 버그가 발생해 현재 고치는 중 입니다.
Custom Library 생성
멀티 모듈로 커스텀 라이브러리를 만들어 본 것은 처음입니다.
라이브러리로 따로 만들어 분리된 작업을 수행하며, 필요로 되는 부분에 대해 각 모듈에서 따로 관리할 수 있는 장점이 좋게 와닿았습니다.
Map SDK 적용 경험
맵 sdk를 통해 맵이 로드되는 시점과 마커를 등록하는 방법 등을 배웠으며, Naver Developer Api를 통해 좌표를 주소로, 주소를 좌표로 받아오면서 Retrofit2를 이용하는 것에도 적응할 수 있었습니다.