정점 분할 : 노드를 상태에 따라 여러 개로 쪼갠다.
5002번째로 푼 문제는 이 문제였습니다. 문제 상황을 간단하게 요약하면 아래와 같습니다. 1순위가 같으면 2순위를 처리하는 것은 나중에 생각해 보도록 합시다. 우리가 원하는 것은 '탑승 비용', 문제에서 설명하는 route cost를 최소화 하는 방법부터 고민해 보겠습니다. 비행기 1이 도시1에서 3을 거쳐서 목적지인 7로 간다고 해 봅시다. 대충 1에서 7로 가는데 3을 경유한다고 보시면 됩니다. 이 경로를 선택하는 비용이 10이라고 해 보겠습니다. 문제에서 설명하는 것에 따르면 1에서 3으로 가는 탑승 비용, 3에서 7로 가는 탑승 비용, 1에서 7로 가는 탑승 비용이 10으로 같습니다. 이 세 경우는 경로 1을 선택해서 갈 수 있는 경우이기 때문입니다. 문제는, 비용 10을 어느 간선에 줄 것이냐..
자료알고/알고리즘
2020. 12. 29. 04:01
최근댓글