d라이브러리

호환마마보다 더 무서운 것이 있었으니, 경로 짜기입니다! 하루에 40개 학급을 무슨 수로 돌아야 할까요? 행사 당일 밥 먹을 시간은 있겠죠…?

4개 지역에서 이벤트를 신청한 학교의 분포를 멍하니 보고 있던 수학동아 팀. 다행히 세종·대전과 대구, 광주의 경우 π-데이 행사 시간이 겹치거나, 신청할 때 연락처를 남기지 않은 경우를 빼면 10곳 내외라 대부분의 학교를 방문할 수 있었습니다.
하지만 90건의 신청이 모인 서울·경기에서 방문할 학교를 고르기란 쉽지 않았지요. 그래서 시간, 위치를 고려해 π-데이 행사를 하는 학교에 많이 갈 수 있고, 동선이 비교적 간단한 경기 하남과 구리시, 서울 일부 지역을 선택했습니다. 따라서 서울·경기와 세종·대전은 12개, 대구와 광주는 8개 학급을 가기로 했지요.
큰 산을 하나 넘었다고 생각했는데, 정말 중요한 단계가 남아 있었습니다. 아침 9시부터 오후 5시까지, 약 8시간 동안 이 장소를 모두 들르기 위해선 학교들 사이의 이동 시간을 계산해 최단 시간이 걸리는 경로를 짜야 했습니다. 
경로 최적화 문제 하면, 외판원 문제(Traveling Salesman Problem, TSP)가 있죠. 가야 할 지점이 정해져 있을 때, 비용 또는 시간을 최소로 쓰는 경로를 찾는 방법입니다. 아일랜드 수학자 윌리엄 해밀턴이 제시한 모든 점을 한 번씩만 지나는 ‘해밀턴 경로’와 비슷한 개념이에요. 저희가 경로를 짜는 것 역시 외판원 문제에 해당합니다. 
외판원 문제는 캐나다 워털루대학교 연구팀이 만든 ‘Concorde(콩코드)’라는 프로그램으로 풀 수 있는데요, 이 프로그램에서는 지점 간의 거리를 기준으로 최단 경로만 계산할 수 있어, 저희가 필요한 최소 시간이 걸리는 경로는 계산할 수 없습니다. 
그래서 지도를 펴고, 직접 경로를 짜봤습니다. 예로 대구 지역의 경로를 한번 볼까요? 대구에서는 π-데이 행사를 하는 ➊안심중학교와 ➍덕원고등학교를 각각 오전 9시 55분과 낮 12시까지 도착해야 합니다. 그래서 출발지를 안심중학교로 정하고 경로를 짜기 시작했지요. 
가장 가까이 있는 지점을 골라 연결한 결과, 안심중-고산중-사월초-덕원고-대구고-효성초-영남중-성지중의 경로를 얻었습니다. 특히 덕원고등학교는 행사 시간인 낮 12시 전에만 도착하면 되기 때문에, 고산중학교와 사월초등학교를 먼저 들르도록 경로를 짰지요. 다른 세 지역도 마찬가지로 이동 시간과 행사 일정을 고려해 짰답니다. 이제 행사 준비 완료!