한국의 모든 술집, 걸어서 한 바퀴? 美 수학자가 ‘최단 경로’ 계산

8만여 곳 가는 데 178일 소요

경찰청 ‘술집 위치정보’ 데이터

컴퓨터 여러 대를 병렬로 연결

44년 걸리는 계산 3개월에 끝내

윌리엄 쿡 캐나다 워털루대 수학과 교수가 한국에 있는 모든 술집 8만1998개를 걸어서 방문하는 최단 거리를 계산했다. 사진은 쿡 교수의 연구에 따른 최단 거리 경로를 나타낸다. 윌리엄 쿡 교수 제공

미국 유명 수학자가 한국에 있는 모든 술집 8만1998개를 걸어서 방문하는 최단 거리를 계산했다. 쉬지 않고 모든 술집을 걸어서 방문하면 178일 1시간 56분 17초가 걸린다.

윌리엄 쿡 캐나다 워털루대 수학과 교수는 이달 8일(현지 시간) 모든 한국 술집 8만1998개를 걸어서 방문하는 최단 경로를 계산하고 증명한 결과를 자신의 홈페이지에 공개했다. 쿡 교수는 조합론과 최적화 분야에서 세계적인 수학자다.

쿡 교수는 ‘외판원 문제(TSP)’라고 불리는 유명한 수학 문제를 도로에서 최적의 경로를 찾는 문제에 적용했다. 외판원 문제란 도시가 여러 개 있을 때 외판원이 모든 도시를 한 번만 지나가면서 전부 방문할 수 있는 가장 짧은 거리를 구하는 문제다. 방문하는 도시의 수가 같더라도 각 도시를 연결하는 경로가 다르고 가장 짧은 거리를 찾아야 하기 때문에 무엇을 대상으로 하느냐에 따라 완전히 다른 문제가 된다.

쿡 교수는 엄상일 기초과학연구원(IBS) 이산수학그룹 CI(Chief Investigator)로부터 제공받은 한국 경찰청의 ‘전국 술집 위치정보’를 이용했다. 주소, 위도, 경도 등이 포함된 전국 술집 위치정보에 따르면 2023년 기준 한국의 술집은 9만680개다. 쿡 교수는 같은 건물에 있는 여러 술집은 1개의 술집이라고 설정하는 등 데이터를 정리해 술집 수를 8만1998개로 설정했다.

쿡 교수는 술집 8만1998개를 이용해 술집 2개씩을 붙여 한 쌍을 만드는 작업을 했다. 술집은 중복으로 등장할 수 있다. 총 33억6179만5003개 쌍이 나왔다. 쿡 교수는 최단 거리를 계산해 주는 공개 시스템인 ‘오픈소스라우팅 머신(OSRM)’을 이용해 각 쌍에 묶인 2개 술집을 서로 걸어서 잇는 최단 거리를 계산했다.

쿡 교수는 방대한 최단 거리 데이터를 조합해 ‘분기한정법(branch and bound)’으로 최적의 경로를 찾아냈다. 분기한정법이란 최적의 답이 될 만한 후보를 나뭇가지처럼 늘어놓고 답이 될 가망이 없는 것들은 가차 없이 잘라버리는 방법이다. 답이 나올 수 있는 범위를 정해두고 범위를 벗어나는 값들을 지워 계산의 양을 줄일 수 있다.

쿡 교수는 3개월에 걸쳐 여러 대의 컴퓨터를 병렬로 이용해 한국 술집 8만1998개를 걸어서 방문하는 최단 경로를 찾아냈다. 병렬로 연결된 각 컴퓨터가 문제를 푸는 데 사용한 시간을 모두 합하면 총 44년이다. 결과에 따르면 최단 경로에 소요되는 시간은 178일 1시간 56분 17초다. 연구 논문은 연말에 나올 예정이다.

쿡 교수는 “이번 문제를 2121개의 하위 문제로 바꿔 계산하는 양을 줄이는 수학적 아이디어로 해결했다”며 “외판원 문제를 길에서 여러 장소를 방문하는 최단 경로를 찾는 문제에 적용한 사례 중 가장 많은 수의 장소를 계산한 것”이라고 말했다. 직전 최고 기록은 2021년 네덜란드의 5만7912개 기념물을 방문하는 연구 결과다.

쿡 교수는 “한국 경찰청이 제공하는 데이터가 정확하고 방대해 한국 술집 정보를 이용하게 됐다”고 말했다. 쿡 교수는 지난해 IBS 방문을 앞두고 한국 학생들을 위한 강연을 준비하면서 이번 문제에 도전하기 시작했다. 엄 CI는 “술집 위치정보를 구매한 가격은 단돈 1000원”이라며 “저렴한 가격으로 훌륭한 수학 결과가 나오는 데 일조해 뿌듯하다”고 했다.

외판원 문제는 수학 문제이지만 실생활을 비롯해 산업계 전반에 적용되고 있다. 택배 물품을 전달하는 최적의 경로, 반도체 기판을 만드는 방법 등에 외판원 문제가 사용된다. 엄 CI는 “외판원 문제를 우주의 수많은 별을 방문하는 최단 경로를 계산하는 데도 적용할 수 있다”며 “외판원 문제에서 방문 대상 숫자를 높이면 최적화를 할 수 있는 새로운 수학적 아이디어를 생각해 낼 수 있다는 의미가 있다”고 말했다.

이채린 동아사이언스 기자 rini113@donga.com

ⓒ 동아일보 & donga.com, 무단 전재 및 재배포 금지