본문 바로가기

알고리즘 문제풀이

SCPC 2017 1차예선 5번 풀이. Covernent

문제 설명(요약)

2N개가 리프 노드를 포함하여 M(>2N)개의 정점을 갖는 트리 T=(V, E)가 있다. 각 엣지에는 양의 가중치가 부여되어 있다. 이 트리의 리프 노드는 1, 2, ..., 2N까지 번호가 붙어 있고, 노드 2N+1, ..., M은 엣지가 2개 이상 연결된 내부 노드이다. 리프 노드 i와 N+i 중 많아야 하나만 선택할 수 있다고 할 때, 이 조건을 만족하는 어떤 부분집합 X에 대해, 이들을 포함하는 최소 연결그래프(서브트리)를 생각할 수 있다. 이 서브트리의 모든 엣지의 가중치의 합을 S(X)라고 하자. 가능한 모든 X를 고려할 때 S(X)의 최댓값을 구하여라.

제약 조건: 2 <= N <= 500, 2N < M < 2,000, 모든 가중치는 1,000,000,000 이하의 자연수

실행 조건: 전체 테스트 케이스는 70개 이하, 실행시간 총합 10초 이하. 메모리 총합 256MB 이하.

* 문제 전문은 www.codeground.org에서 볼 수 있습니다.


부분문제 1 풀이

일단, 어떤 i에 대해 노드 i와 노드 N+i 중 적어도 하나가 최적해에 포함된다. 왜냐면 둘 다 포함하지 않는 경우 둘 중 아무거나 포함시키면 최적해보다 더 큰 트리가 만들어지고, 가중치도 더 커지기 때문이다.

따라서 일단 최적해는 3N개 중에 하나임을 알 수 있다. 모든 가능성을 시도해봄으로써 해결할 수 있다. 시간복잡도는 O(3NM)이므로 N <= 10, M <= 40인 부분문제 1은 해결된다. 하지만 부분문제 2부터는 N의 최댓값이 50 이상이므로 완전탐색으로 해결할 수 없다.


부분문제 2 풀이

인터넷에 보면 Min-Cost Max-Flow (MCMF)로 풀린다는 말이 있어서 생각해보았다. 사실 문제 조건을 보면 자연스럽다. 리프 노드를 선택하는 방법은 유량(Flow)에 해당할 것 같고, 트리의 가중치는 유량을 흘리는 비용(Cost)에 해당할 것 같다. 가중치를 최대화하고 있으므로, 이것의 음수를 생각하면 비용에 해당한다.

하지만 그래프를 어떻게 만들 것인가? 일단, 노드 i와 노드 N+i가 많아야 하나 포함될 수 있다는 조건이 전형적인 플로우 문제 스타일이므로 이 부분부터 모델링해 보자. Supersource를 하나 두고, a(i)라는 노드로 연결하되, 최대 유량을 1만 준다. 그런 다음 a(i)에서 노드 i와 노드 N+i로 연결하면 둘 중 한 곳으로만 1의 유량이 흐를 수 있다.


그 다음에는? 일단 어디엔가 Sink가 있어야 한다. 하지만 Sink를 그냥 막 뚫으면 안 되고, 유량이 어떻게 흐르든지 간에 그 유량이 흐르는 곳들의 비용을 모두 합치면 해당 유량이 나타내는 최소 연결그래프의 비용의 합이 되도록 그래프를 설계해야 한다. 감이 잘 오지 않으므로, 두 개의 리프 노드 A와 B만 선택된 경우를 생각해보자. 이 경우의 최소 연결그래프는 두 노드를 연결하는 선 형태이다. 즉, A에서 출발한 유량이 모두 B로 흘러가면 충분하다는 의미다. 이 경우 A와 B를 잇는 선 상에 아무데나 Sink가 하나 있으면 최적해와 일치하게 된다.


리프 노드 C를 추가로 선택하여 세 개가 되었을 때는 어떤가? C에서 출발하여 A와 B를 잇는 선 위의 한 점에 도달해야 한다. 하지만 A와 B를 잇는 선 상에 Sink가 있으므로, C에서 출발하여 해당 Sink에 도달하지 못할 수 있다. 왜냐면 엣지의 용량 제한을 걸어놓았기 때문이다. 엣지에 Flow를 2 이상 허용하게 되면 해당 엣지의 비용이 중복 계산되므로 1로 제한할 수밖에 없다. 이를 해결하기 위해서는 우회 경로를 뚫으면 된다. 즉 Flow가 더 이상 갈 수 없는 상황이 되었다면, 그 자리에서 더 이상 비용이 있는 간선을 통과하지 않고 Sink로 바로 가는 것이다.


하지만 Sink를 미리 뚫어두는 방법에는 문제가 있다. 왜냐면 어느 위치가 Sink로 작용할 지 미리 알 수 없기 때문이다. 그렇다고 Sink를 두 개 이상 뚫어둘 수도 없다. 그러면 최적해가 제대로 계산되지 않기 때문이다. 이럴 때의 일반적인 해결 방법은 Sink를 하나만 뚫되 계속해서 바꿔가면서 해 보는 것이다. 어떤 노드 P를 Sink로 뚫었을 때, P를 포함하는 최소 트리를 갖는 리프 노드 선택의 경우 유량을 흘리면 최적해가 구해지지만, P를 포함하지 않는 최소 트리를 갖는 리프 노드 선택의 경우 유량을 흘리면 최적해보다 더 큰 가중치, 즉 최적해보다 더 낮은 비용이 구해진다. 우리는 최소 비용을 원하는데, 실제 가능한 최소 비용보다 더 낮은 비용이 구해져서야 문제를 제대로 풀 수가 없다. 따라서 어떤 노드 P를 Sink로 뚫었다면, 반드시 P를 지나가도록 리프 노드를 선택하여야 한다. 그러므로 모든 리프 노드 조합을 시도해보는 방법을 생각할 수 있는데, 이렇게 되면 Sink로 가능한 각 노드에 대해 4 * NC2 = O(N2)개의 조합을 시도해야 한다. 그러므로 MCMF 문제를 총 O(N^3)번 풀어야 하므로 시간 내에 통과하기 어렵다.


하지만 P를 리프 노드로 선택하고 해당 리프 노드는 반드시 포함된다고 가정한다면 최적해보다 더 좋은 가짜 해가 포함되는 일을 막을 수 있다. 모든 최적해는 리프 노드 중 적어도 하나를 반드시 포함하므로, 모든 리프 노드 2N개에 대해 시도해보면 부분문제 2가 해결된다.


다만 MCMF 문제를 2N번 풀어야 하므로 전체 문제는 해결되지 않는다.


부분문제 3 풀이

조금만 생각해보면, 모든 리프 노드를 Sink로 고려할 필요가 없다는 걸 발견할 수 있다. 최적해에는 노드 i나 노드 N+i 중 하나 이상이 반드시 포함되므로, 임의의 i를 하나만 정해서 노드 i와 노드 N+i 이렇게 딱 두 개만 Sink로 고려하면 충분하다.

쓰다 보니 많이 거칠다는 걸 느끼지만, 아이디어가 드러나면 됐다.


내용 보충

* Sink를 정했으면 트리의 각 간선은 Sink 쪽을 향하는 방향으로 도입해야 한다. BFS나 DFS로 해결하면 된다.

* 부분문제 2, 3에서 노드 i를 선택한 경우 Supersource에서 a(i)로는 유량을 보내지 못하도록 해당 간선을 제거하는 처리가 필요하다.