이 문제를 풀어보지는 않았지만 최적해를 분류해보면 다음과 같습니다.
- 두 죄수가 서로 독립된 경로로 빠져나가는 경우
- 두 죄수 중 한 죄수가 다른 죄수 위치로 이동하고, 둘이 같이 빠져나가는 경우
- 두 죄수가 이동하다가 중간에서 만나서 같이 빠져나가는 경우
첫 번째와 두 번째 경우는 죄수가 한 명만 있는 경우처럼 풀 수 있습니다.
따라서 세 번째 경우가 중요합니다.
그런데 세 번째 경우는 결국 그 중간에서 만나는 위치가 중요하게 됩니다.
중간에서 만나는 위치를 P로 고정했다고 하면, 최적해는 결국 두 죄수를 P로 끌고 오는 최소비용에 P와 밖을 연결하는 최소비용으로 주어지게 됩니다.
아마도 이 P를 제3자라고 말씀하신 것 같네요.
도움이 되셨기를 바랍니다!
yg2356 1년 전
문제를 품에 있어서 제3자가 필요한 상황이라고 생각을 못했는데
왜 제3자를 도입해야만 하는건가요?
이 부분이 이해가 잘 가지 않습니다.