🍶 한국의 모든 술집을 걸어서 돌 수 있을까?
상상해보세요. 한국에 있는 모든 술집을 하나도 빠짐없이 도보로 방문하는 여정.
거기에다 가장 효율적인 경로로 술집들을 돌아다닌다고 한다면?
말도 안 되는 얘기처럼 들릴 수 있지만…
이게 실제로 수학적으로 계산되어 ‘최적의 경로’가 완성됐다는 소식입니다.
바로 우리가 이뤄낸 결과이기도 하죠. 🎉
🍺 81,998개의 술집, 33억 개의 거리 계산
우리가 도전한 건 **외판원 문제(TSP)**로 알려진 고전적인 수학 퍼즐입니다.
간단히 말하면, 여러 도시(여기선 술집)를 한 번씩만 방문하고 다시 출발점으로 돌아올 때
가장 짧은 경로를 찾는 문제죠.
- 대상: 한국 전체 81,998개의 술집
- 거리 계산 방식: **OSRM(Open Source Routing Machine)**을 활용해 도보 시간 기준
- 계산한 거리 쌍: 3,361,795,003개
그 결과 나온 경로는 15,386,177초 걸립니다.
시간으로 환산하면 178일 1시간 56분 17초!
🚶 이 경로를 걷는다면 하루도 안 쉬고, 술도 안 마시고, 6개월 동안 계속 걸어야 합니다...
🧠 단순한 재미가 아닙니다, 이건 과학입니다!
“그렇게 많은 경우를 어떻게 다 계산해요?”
사실 가능한 모든 경로를 다 계산하려면 2의 367,308승이라는 어마어마한 조합 수가 나옵니다.
(정확히 계산하려다 컴퓨터가 먼저 지쳐 나가떨어질 수준…)
그래서 저희는 이 문제를 풀기 위해
- ✨ LKH 알고리즘 (가장 좋은 후보를 빠르게 찾기 위한 휴리스틱)
- 📐 Concorde TSP Solver (수학적으로 "이게 진짜 최적"임을 증명) 를 조합해 사용했습니다.
선형 계획법을 활용한 절단 평면 기법까지 도입해,
**“이보다 1초라도 짧은 경로는 존재하지 않는다”**는 걸 증명해냈습니다.
🗺️ 경로는 어디서 볼 수 있나요?
저희가 찾은 경로는 단순히 숫자 나열이 아니라
인터랙티브 지도 형태로 누구나 볼 수 있게 구성돼 있습니다.
- 📍 7개 지역별로 탐색 가능
- 🌈 컬러 지도 or 회색조 선택 가능
- 📌 각 술집 마커, 경로선 시각화
- 🧭 Leaflet + OpenStreetMap 기반
👉 (지도 링크는 계산 페이지에서 확인 가능!)
🤝 협업의 힘
이번 프로젝트는 수많은 협력자들의 도움으로 완성됐습니다.
- 경찰청의 공공 데이터 → 전국 술집 위치 확보
- 엄상일 박사님(기초과학연구원) → 데이터 정제
- IBM CPLEX Optimizer → 수백만 개 선형 계획 문제 처리
- OSRM → 모든 도보 시간 계산
- Leaflet/OpenStreetMap → 지도 시각화
특히 이 프로젝트는 덴마크 로스킬데 대학교와 캐나다 워털루 대학교가 공동으로 진행했습니다.
🧩 단순한 취미? 아닙니다
이 프로젝트는 ‘재미있는 퍼즐’에 그치지 않습니다.
📦 물류 배송, 🚴 라이더 경로 최적화, 🚚 택배 배송 순서 등
실제 산업에서 매우 중요한 문제에 응용될 수 있는 모델이기도 합니다.
참고로, 이전까지 가장 많은 지점을 최적으로 해결한 TSP는
2021년 네덜란드의 57,912개 자전거 경로였는데요.
이번 한국의 81,998개 도보 경로는 그 기록을 훌쩍 넘은 세계 최대 규모입니다.
🎥 더 알고 싶다면?
이 영상에서는 경로 계산의 핵심 원리부터 실제 적용 사례까지 더 깊이 이해할 수 있습니다.
마무리하며
"한국 모든 술집을 걷는다면?"이라는 다소 유쾌한 발상에서 시작한 프로젝트였지만,
그 이면에는 복잡한 수학, 최적화 알고리즘, 수많은 계산이 숨어 있습니다.
실제로 걷기에는 너무나 험난한 여정이지만,
이 여정을 계산으로 마무리했다는 건 큰 의미가 있다고 생각합니다.
여러분도 기회가 된다면 지도 한번 눌러보세요.
여러분 집 근처의 술집도 분명 포함되어 있을 겁니다! 🍶