출발 간격이 35분이면 배 한 척으로 세 편을 맡을 수 있을까요? A와 B 두 항구를 오가는 자체 운항표를 만들어 볼까요? 모든 배는 처음 A에 있어요. 횡단은 정확히 25분, 도착 뒤 준비는 10분이에요. 기다리기는 허용하지만 표에 없는 빈 배 이동은 금지해요.
| 편 | 출발 시각(분) | 원래 방향 | 바꾼 방향 |
|---|---|---|---|
| 1 | 0 | A→B | A→B |
| 2 | 35 | B→A | A→B |
| 3 | 70 | A→B | A→B |
두 표는 출발 시각이 같고 둘째 편의 방향만 달라요. 각 편을 한 번씩 맡도록 배에 색을 붙여 볼까요? 필요한 배의 최소 수가 같을까요?
편 i의 출발 시각을 tᵢ, 출발항을 pᵢ, 도착항을 qᵢ라 해요. 다음 편을 맡을 수 있는 시각 rᵢ와, 이후 편 번호 중 시간 조건을 만족하는 집합 Cₜ, 위치 조건을 만족하는 집합 Cₚ는 다음과 같아요.
같은 배가 바로 이어 맡을 편은 두 조건을 함께 만족하는 교집합 Cₜ∩Cₚ에서 골라야 해요. 원래 표에서는 1편 뒤 B에 25분에 도착해 35분부터 준비가 끝나요. 2편을 맡으면 A에 60분에 도착해 70분부터 3편을 맡아요. 한 척의 기록 1→2→3이 완성되므로 최소 한 척이에요.
바꾼 표의 세 편은 모두 A→B입니다. 한 편을 마친 배는 B에 있고 A로 돌아오는 편이 없어요. 시간 간격은 맞아도 어느 배도 두 편을 맡을 수 없어 최소 세 척이 필요해요. 처음 A에 둔 배 세 척에 한 편씩 배정하면 실제로 돼요. 출발 간격만 보던 계산에 도착항을 표시했을 때 배의 수가 왜 달라지는지 설명해 볼까요?
착안: BC Ferries, Coastal Ferry Services Contract, 2023년까지 개정된 비공식 통합본의 Route12. 두 항구를 잇는 25분 횡단 배경만 참고했어요. 준비 시간·세 편의 표·초기 배치는 자체 조건이며 현재 운항 안내나 실제 함대의 최소 규모를 계산한 것이 아니에요.