d라이브러리

시민들은 생활 쓰레기를 집 앞에 내놓습니다. 쓰레기차는 이를 모아 매립지로 옮겨요. 쓰레기차가 가는 가장 짧은 거리는 어떻게 찾을까요?

쓰레기차가 1대라면, 최단거리는 ‘순회하는 외판원 문제’를 풀면 됩니다. 외판원이 도시 N개를 한 번씩 들렀다 올 때 최단거리를 구하는 문제예요. 외판원을 쓰레기차로, 도시를 쓰레기 배출지로 바꾸면 우리가 풀 문제가 되죠. 배출지가 많을수록 계산량도 커서 보통 근삿값을 구합니다.

그런데 1대만으로는 도시의 쓰레기를 모두 감당할 수 없습니다. 여러 대가 담당할 구역을 나눌 땐 ‘집합 덮개 문제’를 풉니다. 예를 들어 쓰레기차가 4대라면, 모든 배출지를 포함하면서 각 차의 관할구역이 최대한 덜 겹치도록 도시를 4개로 나누는 거죠. 집합 덮개 문제로 관할구역을 정하고 나면, 구역별로 순회하는 외판원 문제를 풀어 최단거리를 구할 수 있습니다.


위험한 쓰레기는 사람을 피해야 해

2017년 6월, 파키스탄 동부 펀자브 주 바하왈푸르의 한 고속도로에서 큰 불이 났습니다. 휘발유를 옮기던 유조차가 뒤집히면서 기름이 유출되자, 수백 명이 이를 가져가려고 몰려들던 중 기름에 불이 붙어 7월 8일까지 218명이 숨졌습니다.

이런 휘발유뿐 아니라 공장이 내놓는 암모니아 같은 위험물질을 옮길 때 교통사고가 나면 끔찍한 피해로 이어집니다. 그러니 최단거리와 함께 위험도도 생각해야 합니다. 교통사고 발생확률이 높거나 사람이 많은 곳은 피해야겠죠.
 

위험도를 계산하는 방법 중 ‘기댓값’을 이용해 봅시다. 기댓값은 어떤 사건이 일어날 확률에 그 사건으로 얻는 이득 혹은 치르는 비용을 곱해 계산합니다. 예를 들어, 트럭이 위험물질을 싣고 점 A에서 점 B로 갈 때 피해 비용의 기댓값은 식㉠와 같습니다. 사고 확률은 과거 기록으로 추정하고, 사고가 날 때 비용은 사람을 대피시키고 현장을 복구하는 데 드는 비용을 예측해 구합니다.

그럼 트럭이 점 A에서 점 C로 갈 때 어떻게 가야 안전할까요? 도로①을 이용할 때 피해 비용의 기댓값을 구해봅시다. 트럭은 AB에서 사고가 나지 않아야 도로①로 지나므로, 도로①에서 사고가 날 확률은 AB에서 사고가 나지 않을 확률과 도로①에서 사고가 날 확률은 곱한 값입니다. 따라서 도로①을 이용할 때 기댓값은 식㉠+식㉡입니다. 같은 방법으로 도로②또는 ③을 지나 점 A에서 점 C까지 갈 때의 기댓값을 각각 구해 가장 작은 길을 택하면 안전합니다.