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

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